Теория языка

  • ЛР
  • ЛЛ
  • зеркальная фотокамера
  • ЛАЛР

Теория языка

В теории языка набор элементарных объектов называется алфавитом. Сочетание элементарных единиц называется словом. Набор слов называется языком и описывается грамматика. Из грамматики можно построить эффективную процедуру (называемую автоматом), позволяющую решить, является ли слово частью языка.

Существуют разные классы языков, соответствующие разным классам грамматик и автоматов. Среди самых простых для изучения класс регулярных языков соответствует регулярным грамматикам и конечным автоматам. Этот класс грамматики обычно используется для описания бесцикловой домашней автоматизации.

Более глобальным классом, чем обычные языки, является класс контекстно-свободных языков, соответствующих контекстно-свободным грамматикам и автоматам выталкивания вниз. Этот класс грамматики, более мощный, чем обычный класс грамматики, обычно используется для домашней автоматизации с известными циклами.

Теория языка полезна для:

  • описывать автоматическое поведение (робототехника, домашняя автоматизация, автоматизация зданий)
  • понимать все язык и его использование (компилятор, ДНК, машинное обучение)
  • Минимизируйте автоматический процесс (интегрированное программное обеспечение, интегрированная плата для аэрокосмической или автомобильной промышленности и т. д.)

Алфавит

Алфавит, обозначаемый А, представляет собой непустое конечное множество символов (букв, знаков, цифр и т.

Слово, определенное в алфавите А, представляет собой конечную последовательность символов/элементов А.

теория языка

Некоторые свойства слов:

  • Длина слова u, определенного в алфавите A, обозначается |u| — количество символов (его кардинальное число), из которых состоит u.
  • |у|я подсчитывает количество вхождений символа j в слово u.
  • Пустое слово, обозначаемое ε, определено во всех алфавитах и является словом длины 0.
  • Множество всех слов, образованных из алфавита A (соответственно всех непустых слов), обозначается A* (соответственно А+).
  • Конкатенация двух слов u и v, отмеченная как uv или uv, представляет собой слово, образованное путем следования символов u за символами v. Степень n слова — это слово, сцепленное n раз.
  • если один или несколько символов в степени +, то это означает, что в слове есть один или несколько символов этого типа (напр. (ab)+=аб…)
  • если один или несколько символов в степени *, то это означает, что в слове ноль или более символов этого типа

теория языка

Пусть u и v — два слова, определенные в алфавите A.

  • u является префиксом v тогда и только тогда, когда существует (потенциально пустое) слово w такое, что uw=v.
  • u является суффиксом v тогда и только тогда, когда существует (потенциально пустое) слово w такое, что wu=v.
  • u является фактором v тогда и только тогда, когда существуют два (потенциально пустых) слова w1 и ш2 такие как ш1эээ2=в.
  • непустое слово u называется примитивным, если уравнение u=vя не допускает решения при i>1.
  • два слова x=uv и y=vu, выведенные друг из друга путем замены префикса и суффикса, называются сопряженными.

Языки

Язык, определенный на алфавите A, представляет собой набор слов, определенных на A. Язык является подмножеством A*.

Установите операции, определенные для языков:
теория языка
  • В союз входят все слова, которые либо содержатся в L1 либо в Л2.
  • Пересечение — это язык, содержащий все слова, содержащиеся сразу в L1 и в л2.
  • Дополнением языка является язык, содержащий все слова, которых нет в этом языке.
  • Разница между двумя языками - это язык, содержащий все слова L1 которых нет в L2.

В дополнение к операциям множества над языками произведение или конкатенация двух языков и определяется языком, содержащим все слова, образованные в результате конкатенации слова L1 за которым следует слово L2. Произведение языков ассоциативно, но не коммутативно.

Сила языка — это последовательная конкатенация этого языка Lнет=ЛЛп-1. Степень 0 образует составной язык пустого слова.

Рассмотрим, например, два языка L1 = {00, 11} и L2 = {0, 1, 01} установлено в {0,1}.
л12 = {000, 001, 0001, 110, 111, 1101}.

Грамматика

Язык можно описать определенным количеством правил: грамматика указывает, как строить предложения, принадлежащие языку (операция в производстве); грамматика также позволяет решить, принадлежит ли данное предложение к языку (функция узнавания).

Грамматика — это четверка G = (T, N, S, R), такая что:

  • T — терминальный словарь, т. е. алфавит, на котором определен язык.
  • N — нетерминальный словарь, т. е. набор символов, не встречающихся в генерируемых словах, но используемых при генерации. Нетерминальный символ обозначает синтаксическую категорию.
  • R представляет собой набор так называемых правил перезаписи или продуцирования вида: u1 → u2, где u1 ∈ (N ∪ T)+ и u2 ∈ (N ∪ )*. Напомним, что + означает наличие как минимум одного элемента, а * означает 0 или более. Интуитивный смысл этих правил состоит в том, что непустая последовательность терминальных или нетерминальных символов u1 может быть заменена возможно пустой последовательностью терминальных или нетерминальных символов u2.
  • S ∈ N — начальный символ или аксиома. Именно с этого нетерминального символа мы начнем порождение слов с помощью правил грамматики.

Когда несколько правил грамматики имеют одинаковую форму в левой части, мы
можно разложить на множители эти различные правила, разделив прямые части вертикальными линиями. Например, набор правил S → ab, S → aSb, S → c можно записать как S → ab | асб | против.

Язык, определенный или сгенерированный грамматикой, представляет собой набор слов, которые можно получить из начального символа, применяя правила грамматики. Более формально введем понятия деривации между формами, это состоит в замене нетерминального символа последовательностью терминальных и нетерминальных символов по правилам грамматики.

Для получения дополнительной информации об операциях между языком и грамматикой обратитесь к таблице ссылок в начале этого курса.

Делиться
ru_RURU