FL&G

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

прикосновение к настоящему...

Основные определения

Определение 1.1.1. Будем называть натуральными числами неотрицательные целые числа. Множество всех натуральных чисел {0, 1, 2, ...} обозначается N.

Определение 1.1.2. Алфавитом называется конечное непустое множество. Его элементы называются символами ( буквами ).

Определение 1.1.3. Словом ( цепочкой, строкой, string) в алфавите $\Sigma$ называется конечная последовательность элементов $\Sigma$ .

Пример 1.1.4. Рассмотрим алфавит $\Sigma$ = {a, b, c}. Тогда baaa является словом в алфавите $\Sigma$ .

Определение 1.1.5. Слово, не содержащее ни одного символа (то есть последовательность длины 0 ), называется пустым словом и обозначается $\varepsilon$ .

Определение 1.1.6. Множество всех слов в алфавите $\Sigma$ обозначается $\Sigma ^*$ .

Замечание 1.1.7. Множество $\Sigma ^*$ счетно. В самом деле, в алфавите $\Sigma$ множество всех слов данной длины конечно, следовательно, $\Sigma ^*$ является объединением счетного числа конечных множеств.

Определение 1.1.8. Множество всех непустых слов в алфавите $\Sigma$ обозначается $\Sigma ^+$ .

Пример 1.1.9. Если $\Sigma$ = {a}, то $\Sigma ^+$ = {a,aa,aaa,aaaa,...}.

Определение 1.1.10. Если $L \subseteq \Sigma ^*$ , то L называется языком (или формальным языком ) над алфавитом $\Sigma$ .

Поскольку каждый язык является множеством, можно рассматривать операции объединения, пересечения и разности языков, заданных над одним и тем же алфавитом (обозначения $L_1 \cup L_2,\; L_1 \cap L_2,\; L_1 - L_2$ ).

Пример 1.1.11. Множество {a, abb} является языком над алфавитом {a, b}.

Определение 1.1.12. Пусть $L \subseteq \Sigma ^*$ . Тогда язык $\Sigma ^* - L$ называется дополнением языка L относительно алфавита $\Sigma$ . Когда из контекста ясно, о каком алфавите идет речь, говорят просто, что язык $\Sigma ^* - L$ является дополнением языка L.

Определение 1.1.13. Если x и y - слова в алфавите $\Sigma$ , то слово xy (результат приписывания слова y в конец слова x ) называется конкатенацией,( катенацией, сцеплением ) слов x и y. Иногда конкатенацию слов x и y обозначают $x \cdot y$ .

Определение 1.1.14. Если x - слово и $n \in N$ , то через xⁿ обозначается слово $\underbrace{ x \cdot x \cdot \ldots \cdot x }_{n \text{ раз}}$ . Положим $x^0 \rightleftharpoons \varepsilon$ (знак $\rightleftharpoons$ читается "равно по определению"). Всюду далее показатели над словами и символами, как правило, являются натуральными числами.

Пример 1.1.15. По принятым соглашениям ba³ = baaa и (ba)³ = bababa.

Пример 1.1.16. Множество $\{ a^k b a^l \mid k \leqslant l \}$ является языком над алфавитом {a,b}. Этот язык содержит слова b, ba, aba, baa, abaa, baaa, aabaa, abaaa, baaaa и т. д.

Определение 1.1.17. Длина слова w, обозначаемая |w|, есть число символов в w, причем каждый символ считается столько раз, сколько раз он встречается в w.

Пример 1.1.18. Очевидно, что |baaa| = 4 и $| \varepsilon | = 0$ .

Определение 1.1.19. Через |w|_a обозначается количество вхождений символа a в слово w.

Пример 1.1.20. Если $\Sigma = \{ a , b , c \}$ , то |baaa|_a = 3, |baaa|_b = 1 и |baaa|_c = 0.

Операции над языками

Определение 1.2.1. Пусть $L_1 , L_2 \subseteq \Sigma ^*$ . Тогда

$L_1 \cdot L_2 \rightleftharpoons \{ x y \mid x \in L_1, \; y \in L_2 \} .$

Язык $L_1 \cdot L_2$ называется конкатенацией языков L₁ и L₂.

Пример 1.2.2. Если L₁ = {a,abb} и L₂ = {bbc,c}, то $L_1 \cdot L_2 = \{ ac , abbc , abbbbc \}$ .

Определение 1.2.4. Пусть $L \subseteq \Sigma ^*$ . Тогда

$\begin{align*} L^0 &\rightleftharpoons \{ \varepsilon \} ,\\ L^n &\rightleftharpoons \underbrace{ L \cdot \ldots \cdot L }_{n \; \text{раз}} \,, \; \text{если} \; n > 0 . \end{align*}$

Пример 1.2.5. Если L = {a^kba^l | 0 < k < l}, то L² = {a^kba^lba^m | 0 < k < l - 1, m > 1}.

Определение 1.2.7. Итерацией языка (Kleene closure) языка L (обозначение L^* ) называется язык

$\bigcup \limits_{ n \in \mathbb{N} } L^n.$

Эта операция называется также звездочкой Клини (Kleene star, star operation).

Пример 1.2.8. Если $\Sigma = \{ a , b \}$ и L = {aa,ab,ba,bb}, то

$L^* = \{ w \in \Sigma ^* \mid | w | \; \vdots \; 2 \} .$

Определение 1.2.11. Обращением или зеркальным образом слова w (обозначается w^R ) называется слово, в котором символы, составляющие слово w, идут в обратном порядке.

Пример 1.2.12. Если w = baaca, то w^R = acaab.

Определение 1.2.13. Пусть $L \subseteq \Sigma ^*$ . Тогда

$L \reverse \rightleftharpoons \{ w \reverse \mid w \in L \} .$

Язык L^R называется обращением языка L.

Определение 1.2.15. Говорят, что слово x - префикс ( начало ) слова y (обозначение $x \sqsubset y$ ), если y = xu для некоторого слова u.

Пример 1.2.16. Очевидно, что $\varepsilon \sqsubset baa$ , $b \sqsubset baa$ , $ba \sqsubset baa$ и $baa \sqsubset baa$ .

Определение 1.2.17. Пусть $L \subseteq \Sigma ^*$ . Тогда через Pref(L) обозначается множество, состоящее из всех префиксов слов языка L:

$\mathrm{Pref} ( L ) \rightleftharpoons \{ x \mid ( \exists y \in L )\, x \sqsubset y \} .$

Множество Pref(L) называется множеством префиксов языка L.

Определение 1.2.18 Говорят, что слово x - суффикс ( конец ) слова y (обозначение $x \sqsupset y$ ), если y = ux для некоторого слова u.

Определение 1.2.19. Пусть $L \subseteq \Sigma ^*$ . Тогда через Suf(L) обозначается множество, состоящее из всех суффиксов слов языка L:

$\mathrm{Suf} ( L ) \rightleftharpoons \{ x \mid ( \exists y \in L )\, x \sqsupset y \} .$

Множество Suf(L) называется множеством суффиксов языка L.

Определение 1.2.20. Говорят, что слово x - подслово (substring) слова y, если y = uxv для некоторых слов u и v.

Определение 1.2.21. Пусть $L \subseteq \Sigma ^*$ . Тогда через Subw(L) обозначается множество, состоящее из всех подслов слов языка L. Множество Subw(L) называется множеством подслов языка L.

Определение 1.2.22. Слово a₁a₂...a_n (длины $n \geqslant 0$ ) называется подпоследовательностью (subsequence) слова y, если существуют такие слова u₀, u₁, ..., u_n, что u₀a₁u₁a₂...a_nu_n = y.

Замечание 1.2.23. Все подслова слова y являются также подпоследовательностями слова y.

Определение 1.2.24. Пусть $L \subseteq \Sigma ^*$ . Тогда через Subseq(L) обозначается множество, состоящее из всех подпоследовательностей слов языка L. Множество Subseq(L) называется множеством подпоследовательностей языка L.

Пример 1.2.25. Рассмотрим язык L = {cba, c} над алфавитом {a, b, c}. Очевидно, что $\mathrm{Subseq} ( L ) = \{ \varepsilon , a , b , c , ba , ca , cb , cba \}$ .

Определение 1.2.26. Функция $f \colon K \to L$ называется биекцией (bijection), если каждый элемент множества L является образом ровно одного элемента множества K (относительно функции f ).

Определение 1.2.27. Множества K и L называются равномощными (of equal cardinality), если существует биекция из K в L.

Гомоморфизмы

Определение 1.3.1. Пусть $\Sigma_1$ и $\Sigma_2$ - алфавиты. Если отображение $h \colon \Sigma_1^* \rightarrow \Sigma_2^*$ удовлетворяет условию $h ( x \cdot y ) = h ( x ) \cdot h ( y )$ для всех слов $x \in \Sigma_1^*$ и $y \in \Sigma_1^*$ , то отображение h называется гомоморфизмом ( морфизмом ).

Замечание 1.3.2. Можно доказать, что если - гомоморфизм, то $h ( \varepsilon ) = \varepsilon$ .

Замечание 1.3.3. Пусть $\Sigma_1 = \{ a , b \}$ и $\Sigma_2 = \{ c \}$ . Тогда отображение $h \colon \Sigma_1^* \rightarrow \Sigma_2^*$ , заданное равенством $h ( w ) = c^{2 | w |}$ , является гомоморфизмом.

Замечание 1.3.4. Каждый гомоморфизм однозначно определяется своими значениями на однобуквенных словах.

Замечание 1.3.5. Если $h \colon \Sigma_1^* \rightarrow \Sigma_2^*$ - гомоморфизм и $L \subseteq \Sigma_1^*$ , то через h(L) обозначается язык $\{ h ( w ) \mid w \in L \}$ .

Пример 1.3.6. Пусть $\Sigma = \{ a , b \}$ и гомоморфизм $h \colon \Sigma ^* \rightarrow \Sigma ^*$ задан равенствами h(a) = abba и $h ( b ) = \varepsilon$ . Тогда

$h ( \{ baa , bb \} ) = \{ abbaabba , \varepsilon \} .$

Определение 1.3.7. Если $h \colon \Sigma_1^* \rightarrow \Sigma_2^*$ - гомоморфизм и $L \subseteq \Sigma_2^*$ , то через h^-1(L) обозначается язык $\{ w \in \Sigma_1^* \mid h ( w ) \in L \}$ .

Пример 1.3.8. Рассмотрим алфавит $\Sigma = \{ a , b \}$ . Пусть гомоморфизм $h \colon \Sigma ^* \rightarrow \Sigma ^*$ задан равенствами h(a) = ab и h(b) = abb. Тогда

$h^{-1} ( \{ \varepsilon , abbb , abbab , ababab \} ) = \{ \varepsilon , ba , aaa \} .$

Порождающие грамматики

Определение 1.4.1. Порождающей грамматикой ( грамматикой типа 0, generative grammar, rewrite grammar) называется четверка $G \rightleftharpoons \langle N , \Sigma , P , S \rangle$ , где N и $\Sigma$ - конечные алфавиты, $N \cap \Sigma = \varnothing$ , $P \subset (N \cup \Sigma) ^+ \times (N \cup \Sigma) ^*$ , P конечно и $S \in N$ . Здесь $\Sigma$ - основной алфавит ( терминальный алфавит ), его элементы называются терминальными символами или терминалами (terminal), N - вспомогательный алфавит ( нетерминальный алфавит ), его элементы называются нетерминальными символами, нетерминалами, вспомогательными символами или переменными (nonterminal, variable), S - начальный символ ( аксиома, start symbol). Пары $( \alpha , \beta ) \in P$ называются правилами подстановки, просто правилами или продукциями (rewriting rule, production) и записываются в виде $\alpha \rightarrow \beta$ .

Пример 1.4.2. Пусть даны множества N = {S}, $\Sigma = \{ a , b , c \}$ , $P = \{ S \rightarrow acSbcS ,\ cS \rightarrow \varepsilon \}$ . Тогда $\langle N , \Sigma , P , S \rangle$ является порождающей грамматикой.

Замечание 1.4.3. Будем обозначать элементы множества $\Sigma$ строчными буквами из начала латинского алфавита, а элементы множества N - заглавными латинскими буквами. Обычно в примерах мы будем задавать грамматику в виде списка правил, подразумевая, что алфавит N составляют все заглавные буквы, встречающиеся в правилах, а алфавит $\Sigma$ - все строчные буквы, встречающиеся в правилах. При этом правила порождающей грамматики записывают в таком порядке, что левая часть первого правила есть начальный символ S.

Замечание 1.4.4. Для обозначения n правил с одинаковыми левыми частями $\alpha \rightarrow \beta_1,\ldots, \alpha \rightarrow \beta_n$ часто используют сокращенную запись $\alpha \rightarrow \beta_1 \mid \ldots \mid \beta_n$ .

Определение 1.4.5. Пусть дана грамматика G. Пишем $\phi \underset { G } {\Rightarrow } \psi$ , если $\phi = \eta \alpha \theta$ , $\psi = \eta \beta \theta$ и $( \alpha \rightarrow \beta ) \in P$ для некоторых слов $\alpha, \; \beta, \; \eta, \; \theta$ в алфавите $N \cup \Sigma$ . Если $\phi \underset{ G }{\Rightarrow } \psi$ , то говорят, что слово $\psi$ непосредственно выводимо из слова $\phi$ .

Замечание 1.4.6. Когда из контекста ясно, о какой грамматике идет речь, вместо $\underset{ G }{\Rightarrow}$ можно писать просто $\Rightarrow$ .

Пример 1.4.7. Пусть

$G = \langle \{ S \} , \{ a , b , c \} , \{ S \rightarrow acSbcS ,\ cS \rightarrow \varepsilon \} , S \rangle .$

Тогда $cSacS \underset{ G }{\Rightarrow } cSa$ .

Определение 1.4.8. Если $\omega_0 \underset{ G }{\Rightarrow } \omega_1 \underset{ G }{\Rightarrow } \ldots \underset{ G }{\Rightarrow } \omega_n$ , где $n \geqslant 0$ , то пишем ${\omega_0 \overset * {\underset{ G }{\Rightarrow}} \omega_n}$ и говорим, что слово $\omega_n$ выводимо из слова $\omega_0$ . Другими словами, бинарное отношение ${\overset * {\underset{ G }{\Rightarrow}}}$ является рефлексивным, транзитивным замыканием бинарного отношения ${\underset{ G }{\Rightarrow}}$ , определенного на множестве $(N \cup \Sigma) ^*$ .

При этом последовательность слов $\omega_0, \omega_1,\ldots, \omega_n$ называется выводом (derivation) слова $\omega_n$ из слова $\omega_0$ в грамматике G. Число n называется длиной ( количеством шагов ) этого вывода.

Замечание 1.4.9. В частности, для всякого слова $\omega \in (N \cup \Sigma) ^*$ имеет место $\omega \oversуt * {\underset{ G }{\Rightarrow}} \omega$ (так как возможен вывод длины 0 ).

Пример 1.4.10. Пусть $G = \langle \{ S \} , \{ a , b \} , \{ S \rightarrow aSa ,\ S \rightarrow b \} , S \rangle$ . Тогда $aSa \overset * {\underset{ G }{\Rightarrow }} aaaaSaaaa$ . Длина этого вывода - 3.

Определение 1.4.11. Язык, порождаемый грамматикой G, - это множество $L(G) \rightleftharpoons \{ \omega \in \Sigma ^* \mid S \overset * {\underset{ G }{\Rightarrow}} \omega \}$ . Будем также говорить, что грамматика G порождает (generates) язык L(G).

Замечание 1.4.12. Существенно, что в определение порождающей грамматики включены два алфавита - $\Sigma$ и N. Это позволило нам в определении 1.4.11 "отсеять" часть слов, получаемых из начального символа. А именно, отбрасывается каждое слово, содержащее хотя бы один символ, не принадлежащий алфавиту $\Sigma$ .

Пример 1.4.13. Если $G = \langle \{ S \} , \{ a , b \} , \{ S \rightarrow aSa ,\ S \rightarrow bb \} , S \rangle$ , то $L(G) = \{ a^n bb a^n \mid n \geqslant 0 \}$ .

Определение 1.4.14. Две грамматики эквивалентны, если они порождают один и тот же язык.

Пример 1.4.15. Грамматика

$\begin{align*} S \; & {\to} \; abS , \\ S \; & {\to} \; a \end{align*}$

и грамматика

$\begin{align*} T \; & {\to} \; aU , \\ U \; & {\to} \; baU , \\ U \; & {\to} \; \varepsilon \end{align*}$

эквивалентны.

Классы грамматик

Определение 1.5.1. Контекстной грамматикой (контекстно-зависимой грамматикой, грамматикой непосредственно составляющих, НС-грамматикой, грамматикой типа 1, context-sensitive grammar, phrase-structure grammar) называется порождающая грамматика, каждое правило которой имеет вид $\eta A \theta \to \eta \alpha \theta$ , где $A \in N$ , $\eta \in (N \cup \Sigma) ^*$ , $\theta \in (N \cup \Sigma) ^*$ , $\alpha \in (N \cup \Sigma) ^+$ .

Пример 1.5.2. Грамматика

$\begin{align*} S \; & {\to} \; T S , & A \; & {\to} \; a , \\ S \; & {\to} \; U S , & T A \; & {\to} \; A A T , \\ S \; & {\to} \; b , & U A b \; & {\to} \; b , \\ T b \; & {\to} \; A b , & U A A A \; & {\to} \; A A U \end{align*}$

не является контекстной (последние три правила не имеют требуемого вида).

Определение 1.5.3. Контекстно-свободной грамматикой ( бесконтекстной грамматикой, КС-грамматикой, грамматикой типа 2, context-free grammar) называется порождающая грамматика, каждое правило которой имеет вид $A \to \alpha$ , где $A \in N$ , $\alpha \in (N \cup \Sigma) ^*$ .

Пример 1.5.4. Грамматика

$\begin{align*} S \; & {\to} \; ASTA , & AT \; & {\to} \; UT , \\ S \; & {\to} \; AbA , & UT \; & {\to} \; UV , \\ A \; & {\to} \; a , & UV \; & {\to} \; TV , \\ bT \; & {\to} \; bb , & TV \; & {\to} \; TA \end{align*}$

является контекстной, но не контекстно-свободной (последние пять правил не имеют требуемого вида).

Определение 1.5.5. Линейной грамматикой (linear grammar) называется порождающая грамматика, каждое правило которой имеет вид $A \to u$ или $A \to u B v$ , где $A \in N$ , $u \in \Sigma ^*$ , $v \in \Sigma ^*$ , $B \in N$ .

Грамматика

$\begin{align*} S \; & {\to} \; TT , \\ T \; & {\to} \; cTT , \\ T \; & {\to} \; bT , \\ T \; & {\to} \; a \end{align*}$

является контекстно-свободной, но не линейной (первые два правила не имеют требуемого вида).

Определение 1.5.7. Праволинейной грамматикой ( рациональной грамматикой, грамматикой типа 3, right-linear grammar) называется порождающая грамматика, каждое правило которой имеет вид $A \to u$ или $A \to u B$ , где $A \in N$ , $u \in \Sigma ^*$ , $B \in N$ .

Пример 1.5.8. Грамматика

$\begin{align*} S \; & {\to} \; aSa , \\ S \; & {\to} \; T , \\ T \; & {\to} \; bT , \\ T \; & {\to} \; \varepsilon \end{align*}$

является линейной, но не праволинейной (первое правило не имеет требуемого вида).

Пример 1.5.9. Грамматика

$\begin{align*} S \; & {\to} \; T , \\ U \; & {\to} \; abba \end{align*}$

праволинейная. Она порождает язык $\varnothing$ .

Пример 1.5.10. Грамматика

$\begin{align*} S \; & {\to} \; aS , & T \; & {\to} \; aT , \\ S \; & {\to} \; bS , & T \; & {\to} \; bT , \\ S \; & {\to} \; aaaT , & T \; & {\to} \; \varepsilon \\ S \; & {\to} \; aabaT , \\ S \; & {\to} \; abaaT , \\ S \; & {\to} \; aabbaT , \\ S \; & {\to} \; ababaT , \\ S \; & {\to} \; abbaaT , \end{align*}$

Пример 1.5.11. Грамматика

$\begin{align*} S \; & {\to} \; \varepsilon , & T \; & {\to} \; abaT , \\ S \; & {\to} \; aaaS , & T \; & {\to} \; baaT , \\ S \; & {\to} \; abbS , & T \; & {\to} \; bbbT , \\ S \; & {\to} \; babS , & T \; & {\to} \; bbaS \\ S \; & {\to} \; aabT , \end{align*}$

праволинейная. Обобщенный вариант языка, порождаемого этой грамматикой, используется в доказательстве разрешимости арифметики Пресбургера.

Определение 1.5.12. Правила вида $\alpha \to \varepsilon$ называются $\varepsilon$ - правилами или эпсилон-правилами.

Лемма 1.5.13. Каждая праволинейная грамматика является линейной. Каждая линейная грамматика является контекстно-свободной. Каждая контекстно-свободная грамматика без $\varepsilon$ -правил является контекстной грамматикой.

Определение 1.5.14. Классы грамматик типа 0, 1, 2 и 3 образуют иерархию Хомского (Chomsky hierarchy).

Определение 1.5.15. Язык называется языком типа 0 ( контекстным языком, контекстно-свободным языком, линейным языком, праволинейным языком ), если он порождается некоторой грамматикой типа 0 (соответственно контекстной грамматикой, контекстно-свободной грамматикой, линейной грамматикой, праволинейной грамматикой). Контекстно-свободные языки называются также алгебраическими языками.

Пример 1.5.16. Пусть дан произвольный алфавит

$\Sigma = \{ a_1 , \ldots , a_n \} .$

Тогда язык $\Sigma ^*$ является праволинейным, так как он порождается грамматикой

$\begin{align*} S \; & {\to} \; \varepsilon , \\ S \; & {\to} \; a_1 S , \\ & \vdots\\ S \; & {\to} \; a_n S . \end{align*}$