Теория языка

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

Контенус

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

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

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

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

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

Алфавит

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

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

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

Длина слова 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 тогда и только тогда, когда существуют два (потенциально пустых) слова w₁ и ш₂ такие как ш₁эээ₂=в.
непустое слово u называется примитивным, если уравнение u=v^я не допускает решения при i>1.
два слова x=uv и y=vu, выведенные друг из друга путем замены префикса и суффикса, называются сопряженными.

Языки

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

Установите операции, определенные для языков:

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

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

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

Рассмотрим, например, два языка L₁ = {00, 11} и L₂ = {0, 1, 01} установлено в {0,1}.

л₁.Л₂ = {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 | асб | против.

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

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