Формальные языки и грамматики

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

Формальные языки:
Множество строк (или слов), составленных из алфавита. Алфавит состоит из конечного набора символов, которые называются символами. Язык — это множество слов, построенных из этих символов.

Пример:
• Алфавит: Σ={a,b} (два символа: a и b).
Язык, состоящий из всех строк, содержащих четное количество символов a: L={ϵ,aa,abba,aabaa,…}.

Грамматики
Набор правил, которые определяют, как можно строить строки формального языка из символов алфавита. Грамматики обычно делятся на несколько типов, в зависимости от их мощности и применимости.

1. Бэкусовская форма (Context-Free Grammar, CFG)
Это один из самых популярных типов грамматик. В CFG правила состоят из замен, где левая часть состоит из одного нетерминала, а правая — из последовательности терминалов и нетерминалов.

Пример: Грамматика для арифметических выражений:
E → E + T
E → E - T
E → T
T → T * F
T → T / F
T → F
F → ( E )
F → number
Здесь:
• E,T,F — нетерминалы.
• +,−,∗,/,(,),number — терминалы.
• Применяя эти правила, мы можем строить выражения, такие как number+number∗number.

2. Грамматики типа 0 (Rug grammar)
Это самая общая форма грамматик, где правила могут быть произвольными, и левые части правил могут содержать несколько символов, в том числе нетерминалы.

3. Грамматики типа 1 (Context-sensitive grammar)
Правила грамматики могут заменять строку, состоящую из нескольких символов, только если на определенной позиции в строке находится подходящий контекст.

4. Грамматики типа 2 (Context-free grammar)
В этих грамматиках правила заменяют один нетерминал на строку из терминалов и нетерминалов, не завися от контекста. Это наиболее популярный тип грамматик, применяемых в компиляторах и других системах.

5. Грамматики типа 3 (Regular grammar)
Самые простые грамматики, где правила имеют ограниченную форму. Например, они могут быть описаны с помощью регулярных выражений.