Języki bezkontekstowe

Wstęp

W tym wykładzie poznamy gramatyki bezkontekstowe i opisywaną przez nie klasę języków bezkontekstowych. Gramatyki bezkontekstowe są formalizmem służącym do opisu składni -- podobnie jak wyrażenia regularne. Podobnie również jak wyrażenia regularne są maksymalnie uproszczonym formalizmem, a wzorce są ich rozbudowaną wersją przeznaczoną do praktycznych zastosować, tak i gramatyki bezkontekstowe mają swoją rozbudowaną wersję przeznaczoną do praktycznych zastosowań. Są to: notacja Backusa-Naura (BNF, ang. Backus-Naur form) oraz rozszerzona notacja Backusa-Naura (EBNF, ang. extended Backus-Naur form). Jest bardzo prawdopodobne, że Czytelnik zetknął się z nimi. Notacje te są zwykle używane w podręcznikach do ścisłego opisu składni języków programowania.

Będziemy również badać właściwości klasy języków, które można opisać gramatykami bezkontekstowymi -- tzw. klasy języków bezkontekstowych. Jak zobaczymy, siła wyrazu gramatyk bezkontekstowych będzie większa niż wyrażeń regularnych i automatów skończonych. Inaczej mówiąc, klasa języków bezkontekstowych zawiera klasę języków regularnych.

BNF

W pierwszym przybliżeniu BNF jest formalizmem przypominającym definicje nazwanych wzorców ze specyfikacji dla Lex'a. Główna różnica polega na tym, że zależności między poszczególnymi nazwami mogą być rekurencyjne.

Specyfikacja w BNF-ie określa składnię szeregu konstrukcji składniowych, nazywanych też nieterminalami. Każda taka konstrukcja składniowa ma swoją nazwę. Specyfikacja składa się z szeregu reguł (nazywanych produkcjami), które określają jaką postać mogą przybierać konstrukcje składniowe. Nazwy konstrukcji składniowych ujmujemy w trójkątne nawiasy $\bnf{\dots}$. Produkcje mają postać:

<definiowana konstrukcja> ::= wyrażenie opisujące definiowaną konstrukcję

Wyrażenie opisujące definiowaną konstrukcję może zawierać:

• $\bnf{konstrukcja}$ -- nazwy konstrukcji, w tym również definiowanej, rekurencyjne zależności są dozwolone,
• tekst, ujęty w cudzysłów, który pojawia się dosłownie w danej konstrukcji,
• $\dots \vert \dots$ -- oddziela różne alternatywne postaci, jakie może mieć dana konstrukcja,
• $[\dots]$ -- fragment ujęty w kwadratowe nawiasy jest opcjonalny.

Produkcje traktujemy jak możliwe reguły przepisywania -- nazwę konstrukcji stojącej po lewej stronie produkcji możemy zastąpić dowolnym napisem pasującym do wyrażenia podanego po prawej stronie. Każdej konstrukcji składniowej odpowiada pewien język. Składa sie on z wszystkich tych napisów, które można uzyskać zaczynając od nazwy konstrukcji i stosując produkcje, aż do momentu uzyskania napisu, który nie zawiera już żadnych nazw konstrukcji.

Przykład

BNF może służyć do opisywania składni najrozmaitszych rzeczy. Oto opis składni adresów pocztowych:

<adres> ::= <adresat> <adres lokalu> <adres miasta> <adres kraju>
<adresat> ::= ["W.P." |"Sz.Pan."] <napis> ","
<adres lokalu> ::= <ulica> <numer> [ "/" <numer> ] ["m" <numer> |"/" <numer> ] ","
<adres miasta> ::=[ <kod> ] <napis>
<adres kraju> ::=[ "," <napis> ]
<kod> ::= <cyfra> <cyfra> "-" <cyfra> <cyfra> <cyfra>
<cyfra> ::= "0" |"1" |"2" |"3" | "4" |"5" |"6" |"7" | "8" |"9"
<numer> ::= <cyfra> [ <numer> ]

Specyfikacja ta nie jest oczywiście kompletna, gdyż nie definiuje czym jest napis. Zwróćmy uwagę na to, że definicja numer jest rekurencyjna.

Gramatyki bezkontekstowe

Gramatyki bezkontekstowe są uproszczoną wersją notacji BNF. Konstrukcje składniowe nazywamy tu nieterminalami lub symbolami nieterminalnymi i będziemy je oznaczać wielkimi literami alfabetu łacińskiego: A, B, ..., X, Y, Z. Wśród nieterminali jest jeden wyróżniony symbol, nazywany aksjomatem. To właśnie język związany z tym nieterminalem opisuje gramatyka.

Oprócz nieterminali używamy również terminali (symboli terminalnych) -- są to znaki stanowiące alfabet opisywanego przez gramatykę języka. Będziemy je oznaczać małymi literami alfabetu łacińskiego: a, b, ....

Produkcje w gramatykach bezkontekstowych mają bardzo prostą postać: $A \to \alpha$, gdzie A to nieterminal, a $\alpha$ to słowo, które może zawierać terminale i nieterminale. Produkcja taka oznacza, że nieterminal A możemy zastąpić napisem $\alpha$. Dla jednego nieterminala możemy mieć wiele produkcji. Oznacza to, że możemy je dowolnie stosować. Zwykle zamiast pisać:

$$\begin{eqnarray*} A &\to& \alpha \\ A &\to& \beta \\ & \vdots & \\ A &\to& \gamma \end{eqnarray*}$$

Będziemy pisać krócej:

$$A \to \alpha \;\vert\;\beta \;\vert\;\dots \;\vert\;\gamma$$

Przykład

Zanim formalnie zdefiniujemy gramatyki bezkontekstowe i opisywane przez nie języki, spójrzmy na gramatykę opisującą język: $\{a^nb^n: n \ge 0\}$.

$$A \to aAb \;\vert\;\varepsilon$$

Oto sekwencja zastosować produkcji, która prowadzi do uzyskania słowa aaabbb:

$$A \to aAb \to aaAbb \to aaaAbbb \to aaabbb$$

Trzykrotnie stosowaliśmy tutaj produkcję $A \to aAb$, aby na koniec zastosować $A \to \varepsilon$.

Przykład ten pokazuje, że gramatyki bezkontekstowe mogą opisywać języki, które nie są regularne.

Definicja

Gramatyka bezkontekstowa, to dowolna taka czwórka $G=\angles{N, \Sigma, P, S}$, gdzie:

• N to (skończony) alfabet symboli nieterminalnych,
• $\Sigma$ to (skończony) alfabet symboli terminalnych, $\Sigma \setint N = \emptyset$,
• P to skończony zbiór produkcji, reguł postaci $A \to \alpha$ dla $A \in N$, $\alpha \in (N \setsum \Sigma)^*$,
• $S \in N$ to aksjomat wyróżniony symbol nieterminalny.

Zwykle nie będziemy podawać gramatyki jako formalnej czwórki. Zamiast tego będziemy podawać zbiór produkcji. Zwykle, w sposób niejawny z produkcji wynika zbiór nieterminali i terminali. Jeżeli nie będzie oczywiste, który nieterminal jest aksjomatem, będziemy to dodatkowo zaznaczać.

Definicja

Niech $G=\angles{N, \Sigma, P, S}$ będzie ustaloną gramatyką bezkontekstową. Przez $\to$ będziemy oznaczać zbiór produkcji P traktowany jako relacja, $\to \subseteq N \times (N \setsum \Sigma)^*$. Przez $\to^*$ będziemy oznaczać zwrotno-przechodnie domknięcie $\to$, $\to^* \subseteq (N \setsum \Sigma)^* \times (N \setsum \Sigma)^*$.

Relacja $\to$ opisuje pojedyncze zastosowanie produkcji, jako relacja między nieterminalem, a zastępującym go słowem. Relacje $\to^*$ opisuje co można zrobić stosując dowolną liczbę (łącznie z zero) dowolnych produkcji. Możemy też przedstawić sobie relację $\to^*$ jako skrót do wielokrotnego iterowania relacji $\to$:

Gramatyka opisuje język złożony z tych wszystkich słów (nad alfabetem terminalnym), które możemy uzyskać z aksjomatu stosując produkcje.

Definicja

Niech $G=\angles{N, \Sigma, P, S}$ będzie ustaloną gramatyką bezkontekstową. Język generowany (lub opisywany) przez gramatykę G, to:

$$L(G) = \{x \in \Sigma^* : S \to^* x\}$$

Alternatywnie, L(G) to zbiór takich słów $x \in \Sigma^*$, dla których istnieją ciągi słów (z_i), $z_i \in (N \setsum \Sigma)^*$ takie, że:

$$S = z_0 \to z_1 \to \dots \to z_k = x$$

Ciąg (z_i) nazywamy wyprowadzeniem słowa x (w gramatyce G).

Definicja

Powiemy, że język jest bezkontekstowy, jeżeli istnieje generująca go gramatyka.

Wyprowadzenie stanowi coś w rodzaju dowodu, że dane słowo faktycznie należy do języka generowanego przez gramatykę. Istnieje jeszcze inny, bardziej strukturalny, sposób ilustrowania jak dane słowo można uzyskać w danej gramatyce. Jest to drzewo wyprowadzenia.

Definicja

Drzewo wyprowadzenia, to sposób ilustrowania jak dane słowo może być wyprowadzone w danej gramatyce, w postaci drzewa. Drzewo wyprowadzenia musi spełniać następujące warunki:

• W korzeniu drzewa znajduje się aksjomat.
• W węzłach wewnętrznych drzewa znajdują się nieterminale, a w liściach terminale lub słowa puste $\varepsilon$.
• Jeśli w danym węźle mamy nieterminal X, a w jego kolejnych synach mamy $x_1, x_2, \dots, x_k$, to musi zachodzić $X \to x_1 x_2 \dots x_k$.
• Terminale umieszczone w liściach, czytane od lewej do prawej, tworzą wyprowadzone słowo.

Przyjrzyjmy się zdefiniowanym powyżej pojęciom na przykładach:

Przykład

Weźmy gramatykę generującą język $\{a^nb^n: n \ge 0\}$:

$$A \to aAb \;\vert\;\varepsilon$$

Wyprowadzenie słów aaabbb ma postać:

$$A \to aAb \to aaAbb \to aaaAbbb \to aaabbb$$

a jego drzewo wyprowadzenia wygląda następująco:

$$\xymatrix{ & A \ar@{-}[dl] \ar@{-}[d] \ar@{-}[dr] \\ a &... ...\ar@{-}[dr] & b\\ a & A \ar@{-}[d] & b\\ & \varepsilon }$$

Przykład

Oto gramatyka generująca język palindromów nad alfabetem {a,b,c}:

$$S \to aSa \;\vert\;bSb \;\vert\;cSc \;\vert\; a \;\vert\;b \;\vert\;c \;\vert\;\varepsilon$$

Weźmy słowo abbcbba. Oto jego wyprowadzenie i drzewo wyprowadzenia:

$$S \to aSa \to abSba \to abbSbba \to abbcbba$$

$$\xymatrix{ & S \ar@{-}[dl] \ar@{-}[d] \ar@{-}[dr] \\ a &... ...ar@{-}[d] \ar@{-}[dr] & b\\ b & S \ar@{-}[d] & b\\ & c }$$

Przykład

Przyjrzyjmy się językowi złożonemu z poprawnych wyrażeń nawiasowych (dla czytelności zbudowanych z nawiasów kwadratowych). Język ten możemy zdefiniować na dwa sposoby. Po pierwsze, wyrażenia nawiasowe, to takie ciągi nawiasów, w których:

• łączna liczba nawiasów otwierających i zamykających jest taka sama,
• każdy prefiks wyrażenia nawiasowego zawiera przynajmniej tyle nawiasów otwierających, co zamykających.

Jeżeli zdefiniujemy funkcje L(x) = #_[(x) i R(x) = #_](x), to język wyrażeń nawiasowych możemy zdefiniować następująco:

$$W = \{x \in \{[,]\}^*: L(x)= R(x) \mbox{ i dla każdego prefiksu $y$ słowa $x$ mamy} L(y) \ge R(y) \}$$

Drugi sposób zdefiniowania języka wyrażeń nawiasowych, to podanie gramatyki bezkontekstowej.

$$S \to [S] \;\vert\;SS \;\vert\;\varepsilon$$

Oznaczmy tę gramatykę przez G. Oto przykładowe drzewo wyprowadzenia dla wyrażenia nawiasowego [[][[]]]:

$$\xymatrix{ & & S \ar@{-}[dl] \ar@{-}[d] \ar@{-}[dr] \\ &... ... \varepsilon & [ & S \ar@{-}[d] & ] \\ & & & \varepsilon }$$

Pokażemy, że obie definicje są sobie równoważne. W tym celu pokażemy najpierw, że każde słowo, które można wyprowadzić w G należy do W, a następnie, że każde słowo z W można wyprowadzić w G.

To, że $L(G) \subseteq W$ będziemy dowodzić przez indukcję ze względu na długość wyprowadzenia.

1. Jedynym słowem jakie można wyprowadzić w jednym kroku jest $\varepsilon$. Oczywiście $\varepsilon \in W$.
2. Załóżmy, że wyprowadzenie ma postać $S \to [S] \to^* [x]$. Z założenia indukcyjnego x jest wyrażeniem nawiasowym. W takim razie [x] też, gdyż:
   
   L([x]) = L(x)+1 = R(x)+1 = R([x])
   
   
   oraz dla każdego prefiksu y słowa x mamy:
   
   $$L([y) = L(y) + 1 > L(y) \ge R(y) = R([y)$$
   
   

3. Załóżmy, że wyprowadzenie ma postać:
   
   $$\xymatrix{ S \ar[r] & SS \ar[dl]_>{*} \ar[dr]^>{*} \\ x & & y }$$
   
   
   Z założenia indukcyjnego x i y są wyrażeniami nawiasowymi. W takim razie xy też, gdyż:
   
   L(xy) = L(x)+L(y) = R(x)+R(y) = R(xy)
   
   
   oraz dla każdego prefiksu z słowa y mamy:
   
   $$L(xz) = L(x) + L(z) \ge L(x) + R(z) = R(x) + R (z) = R(xz)$$
   
   

Z zasady indukcji otrzymujemy $L(G) \subseteq W$.

Pokażemy teraz, że $W \subseteq L(G)$. Dowód będzie przebiegał przez indukcję po długości słowa.

1. Mamy $\varepsilon \in W$ oraz $S \to \varepsilon$.
2. Niech $x \in W$, |x| > 0, $x = a_1 a_2 \dots a_k$. Określmy funkcję $f:\{0,1,\dots, k\} \to \Nat$:
   
   $$f(i) = L(a_1\dots a_i) - R(a_1\dots a_i)$$
   
   
   Zauważmy, że z tego, że x jest wyrażeniem nawiasowym wynika, że:
   
   f(0) = f(k) = 0
   
   
   
   
   $$f(i) \ge 0$$
   
   
   Mamy dwa możliwe przypadki:
   • Dla pewnego 0 < i < k mamy f(i) = 0. Wówczas $a_1\dots a_i$ oraz $a_{i+1}\dots a_k$ są wyrażeniami nawiasowymi. Stąd:
     
     $$S \to SS \to^* a_1\dots a_i\;a_{i+1}\dots a_k = x$$
     
     

   • Dla wszystkich 0 < i < k mamy f(i) > 0. Wówczas $a_2\dots a_{k-1}$ jest wyrażeniem nawiasowym. Stąd:
     
     $$S \to [S] \to^* [a_2\dots a_{k-1}] = x$$
     
     

   Tak więc $x \in L(G)$.

Na mocy zasady indukcji uzyskujemy $W \subseteq L(G)$. Tak więc W = L(G).

Często chcemy, aby gramatyka nie tylko opisywała język, ale również jego strukturę. Wymagamy wówczas, aby gramatyka była dodatkowo jednoznaczna.

Definicja

Powiemy, że gramatyka G jest jednoznaczna, gdy dla każdego słowa $x \in L(G)$ istnieje tylko jedno drzewo wyprowadzenia słowa x w gramatyce G.

Jeśli gramatyka jest jednoznaczna, to drzewa wyprowadzeń jednoznacznie określają strukturę (składniową) słów z języka. Nadal oczywiście słowa mogą mieć wiele wyprowadzeń, ale różnią się one tylko kolejnością stosowanych produkcji, a nie strukturą wyprowadzania słowa.

Przykład

Oto gramatyka opisująca proste wyrażenia arytmetyczne:

$$\begin{eqnarray*} S &\to& S+S \;\vert\;S-S \;\vert\;S*S \;\vert\; S/S \;\vert\... ...ert\;4 \;\vert\;5 \;\vert\;6 \;\vert\;7 \;\vert\;8 \;\vert\;9 \end{eqnarray*}$$

Gramatyka ta jest niestety niejednoznaczna. Na przykład, wyrażenie 42 + 5 * 2 ma dwa różne drzewa wyprowadzenia:

$$\xymatrix{ & & S \ar@{-}[dl] \ar@{-}[d] \ar@{-}[dr] \\ &... ... & & C \ar@{-}[d] & 2 \\ 4 & C \ar@{-}[d] & & 5\\ & 2 }$$

Struktura wyrażenia ma wpływ na sposób jego interpretacji. Drzewo wyprowadzenia po lewej prowadzi do wartości wyrażenia 52, a to po prawej do 94. Wszędzie tam, gdzie gramatyka opisuje składnię języka, któremu towarzyszy ściśle zdefiniowana semantyka, będziemy chcieli, aby była to jednoznaczna gramatyka.

W przypadku wyrażeń arytmetycznych musimy ustalić kolejność wiązania operatorów, oraz wymusić, aby operatory były albo lewostronnie, albo prawostronnie łączne. Oto jednoznaczna gramatyka wyrażeń arytmetycznych:

$$\begin{eqnarray*} E &\to& E+S \;\vert\;E-S \;\vert\;S \\ S &\to& S*F \;\vert\... ...ert\;4 \;\vert\;5 \;\vert\;6 \;\vert\;7 \;\vert\;8 \;\vert\;9 \end{eqnarray*}$$

W tej gramatyce analizowane wyrażenie ma tylko jedno drzewo wyprowadzenia:

$$\xymatrix{ & & E \ar@{-}[dl] \ar@{-}[d] \ar@{-}[dr] \\ &... ...] & C \ar@{-}[d] & & 2 \\ 4 & C \ar@{-}[d] & 5 \\ & 2 }$$

Języki regularne a bezkontekstowe

Pokażemy teraz, że wszystkie regularne są bezkontekstowe. Jak już wcześniej widzieliśmy, odwrotne stwierdzenie nie jest prawdziwe, gdyż aⁿb ⁿ jest językiem bezkontekstowym, ale nie regularny.

Definicja

Gramatyka (prawostronnie) liniowa, to taka, w której wszystkie produkcje mają postać: $A \to \alpha B$ lub $A \to \alpha$, dla $A,B \in N$ i $\alpha \in \Sigma^*$.

Gramatyka silnie (prawostronnie) liniowa, to taka, w której wszystkie produkcje mają postać: $A \to aB$ lub $A \to \varepsilon$, dla $A,B \in N$ i $a \in \Sigma$.

Okazuje się, że gramatyki liniowe i silnie liniowe opisują dokładnie klasę języków regularnych.

Dowód:

Pokażemy, jak gramatykę liniową przerobić na równoważną jej gramatykę silnie liniową. Następnie pokażemy jak można gramatykę silnie liniową przekształcić na równoważny jej niedeterministyczny automat skończony i vice versa.

Żeby gramatykę liniową przerobić na silnie liniową, musimy zastąpić produkcje postaci $A \to a_1\dots a_kB$ (dla k>1) oraz produkcje postaci $A \to B$, równoważnymi jej produkcjami odpowiednimi dla gramatyki silnie liniowej.

Jeżeli mamy w gramatyce produkcję postaci $A \to B$, to dla każdej produkcji postaci $B \to \alpha$ dodajemy do gramatyki produkcję $A \to \alpha$. Krok ten powtarzamy tak długo, jak długo wprowadza on nowe produkcje. Następnie usuwamy wszystkie produkcje postaci $A \to B$. W ten sposób uzyskujemy gramatykę generującą ten sam język, ale nie zawięrającą produkcji postaci $A \to B$.

Dla każdej produkcji postaci:

$$A \to a_1\dots a_kB$$

(dla k>1) dodajemy do gramatyki nowe terminale $A_1, \dots, A_{k-1}$, a samą produkcję zastępujemy produkcjami:

$$\begin{eqnarray*} A &\to& a_1A_1\\ A_1 &\to& a_2A_2\\ &\vdots&\\ A_{k-1} &\to& a_kB \end{eqnarray*}$$

Podobnie, dla każdej produkcji postaci (dla k>1):

$$A \to a_1\dots a_k$$

dodajemy do gramatyki nowe terminale $A_1, \dots, A_k$, a samą produkcję zastępujemy produkcjami:

$$\begin{eqnarray*} A &\to& a_1A_1\\ A_1 &\to& a_2A_2\\ &\vdots&\\ A_{k-1} &\to& a_kA_k\\ A_k &\to& \varepsilon \end{eqnarray*}$$

1. Gramatykę liniową można sprowadzić do silnie liniowej.
2. Gramatykę silnie liniową można przerobić na automat niedeterministyczny.
3. Automat niedeterministyczny można przerobić na gramatykę silnie liniową.

W rezultacie uzyskujemy gramatykę akceptującą ten sam język, ale silnie liniową.

Zauważmy, że jeśli gramatyka jest silnie liniowa (lub liniowa), to w wyprowadzeniu pojawia się na raz tylko jeden nieterminal, i to zawsze na samym końcu słowa. Konstruując niedeterministyczny automat skończony równoważny danej gramatyce silnie liniowej opieramy się na następującej analogii: Miech $G=\angles{N, \Sigma, P, S}$ będzie daną gramatyką silnie liniową. Stanami automatu będą nieterminale gramatyki N. Dla każdego słowa $x \in \Sigma^*$ i $A \in N$, takich, że $S \to^* xA$ nasz automat po wczytaniu słowa x będzie mógł przejść do stanu A. Formalnie konstrukcja naszego automatu M wygląda następująco $M=(N, \Sigma, \delta, \{S\}, F)$, gdzie:

$$F = \{A : A \to \varepsilon \in P\}$$

oraz:

$$\delta(A,a) = \{ B \in N : A \to aB \in P\}$$

Można pokazać (przez indukcję po długości słowa), że:

$$\delta^*(A,x) = \{ B \in N : A \to^* xB \}$$

Stąd:

$$\begin{eqnarray*} L(M) &=& \{x \in \Sigma^* : \delta^*(S,x) \setint F \neq \e... ...silon \in P\} =\\ &=& \{x \in \Sigma^* : S \to^* x\} = L(G) \end{eqnarray*}$$

Tak więc faktycznie języki generowane przez gramatyki silnie liniowe są regularne.

Co więcej, powyższą konstrukcję można odwrócić. Jeśli $M=(Q, \Sigma, \delta, \{s\}, F)$ jest danym niedeterministycznym automatem skończonym (z jednym stanem początkowym), to równoważna mu gramatyka silnie liniowa ma postać $G=\angles{Q, \Sigma, P, s}$, gdzie P zawiera produkcje postaci:

$$\begin{array}{rclcl} q &\to& \varepsilon &\mbox{ dla }& q ... ...& p,q \in Q, a \in \Sigma, p \in \delta (q,a) \end{array}$$

Ponownie można pokazać (przez indukcję po długości słowa), że:

$$\delta^*(q,x) = \{ p \in Q : q \to^* xp \}$$

Stąd:

$$\begin{eqnarray*} L(G) &=& \{x \in \Sigma^* : s \to^* x\} = \\ &=& \{x \in \... ...in \Sigma^* : \delta^*(S,x) \setint F \neq \emptyset \} = L(M) \end{eqnarray*}$$

Tak więc dla wszystkich języków regularnych istnieją generujące je gramatyki silnie liniowe. Tym samym pokazaliśmy, że klasa języków regularnych zawiera się ściśle w klasie języków bezkontekstowych.

Przykład

Rozważmy automat skończony akceptujący język $(ab)^* \;\vert\;(aa)^*$:

Jest on równoważny gramatyce silnie liniowej postaci:

$$\begin{eqnarray*} S &\to& aP \;\vert\;aR \;\vert\;\varepsilon \\ P &\to& bQ \... ...varepsilon \\ R &\to& aT \\ T &\to& aR \;\vert\;\varepsilon \end{eqnarray*}$$

Oto wyprowadzenie przykładowego słowa abab:

$$S \to aP \to abQ \to abaP \to ababQ \to abab$$

Jak widać, odpowiada ono dokładnie obliczeniu automatu akceptującemu słowo abab.

Jeśli wystarczy nam, aby gramatyka była tylko liniowa, to wystarczy mniejsza liczba nieterminali:

$$\begin{eqnarray*} S &\to& abQ \;\vert\;aaT \;\vert\;\varepsilon \\ Q &\to& abQ \;\vert\;\varepsilon \\ T &\to& aaT \;\vert\;\varepsilon \end{eqnarray*}$$

A oto wyprowadzenie przykładowego słowa abab:

$$S \to abQ \to ababQ \to abab$$

Przykład

Niech A będzie językiem złożonym ze słów nad alfabetem {a,b} parzystej długości i różnych od $\varepsilon$:

$$A = \{x \in \{a,b\} : \vert x\vert > 0 \andalso \vert x\vert \mod 2 = 0\}$$

Język ten jest akceptowany przez następujący automat:

Na podstawie tego automatu można stworzyć następującą gramatykę liniową (ale nie silnie liniową) generującą język A:

$$\begin{eqnarray*} S &\to& aX \;\vert\;bX \\ X &\to& aaX \;\vert\;abX \;\vert\;baX \;\vert\;bbX \;\vert\;a \;\vert\;b \end{eqnarray*}$$

Na przykład, słowo abbaaa ma w niej następujące wyprowadzenie:

$$S \to aX \to abbX \to abbaaX \to abbaaa$$

Automat ten jest również równoważny następującej gramatyce silnie liniowej:

$$\begin{eqnarray*} S &\to& aX \;\vert\;bX \\ X &\to& aY \;\vert\;bY \;\vert\;aZ \;\vert\;bZ \\ Y &\to& aX \;\vert\;bX \\ Z &\to& \varepsilon \end{eqnarray*}$$

Słowo abbaaa ma w tej gramatyce następujące wyprowadzenie:

$$S \to aX \to abY \to abbX \to abbaY \to abbaaX \to abbaaaZ \to abbaaa$$

Jak widać, wyprowadzenie w gramatyce silnie liniowej dokładnie odpowiada akceptującemu obliczeniu automatu skończonego. Wyprowadzenie w gramatyce liniowej (ale nie silnie liniowej) również odpowiada akceptującemu obliczeniu automatu, ale jeden krok w wyprowadzeniu może odpowiadać kilku krokom automatu.

Podsumowanie

W tym wykładzie poznaliśmy języki i gramatyki bezkontekstowe wraz z podstawowymi związanymi z nimi pojęciami. Pokazaliśmy też, że klasa języków bezkontekstowych zawiera ściśle w sobie klasę języków regularnych.

Skorowidz

• BNF -- notacja Backusa-Naura, formalizm służący do opisu składni, oparty na gramatykach bezkontekstowych. Zobacz też artykuł w Wikipedii.

• Drzewo wyprowadzenia -- drzewo potwierdzające, że dane słowo należy do języka generowanego przez daną gramatykę; odzwierciedla również strukturę składniową słowa.

• Gramatyka bezkontekstowa -- formalizm do opisu języków.

• Gramatyka liniowa -- gramatyka bezkontekstowa, w której występują produkcje jedynie postaci $A \to \alpha B$ lub $A \to \alpha$ (dla $A,B \in N$ i $\alpha \in \Sigma^*$). Gramatyki liniowe opisują języki regularne.

• Gramatyka silnie liniowa -- gramatyka bezkontekstowa, w której występują produkcje jedynie postaci $A \to aB$ lub $A \to \varepsilon$ (dla $A,B \in N$ i $a \in \Sigma$). Gramatyki silnie liniowe opisują języki regularne.

• Język generowany przez gramatykę bezkontekstową -- to język złożony z tych słów $x \in \Sigma^*$, które można wyprowadzić z aksjomatu S, $S \to^* x$.

• Wyprowadzenie -- ciąg słów potwierdzający, że dane słowo należy do języka generowanego przez daną gramatykę.

Praca domowa

1. (6p.) Podaj gramatykę bezkontekstową generującą język $\{a^n b^{n+k} c^k : n,k \geq 1 \}$. Podaj drzewo wyprowadzenia dla słowa aabbbbbccc.
2. (4p.) Podaj liniową gramatykę generująca język $ab(b^* \;\vert\;a^*)$.

Ćwiczenia

1. Dla gramatyki:
   
   $$\begin{eqnarray*} S &\to& aB \vert Ab \vert SS \\ A &\to& a \vert aS \\ B &\to& b \vert Sb \end{eqnarray*}$$
   
   i słowa aabbab:
   • podaj jego wyprowadzenie,
   • podaj jego drzewo wyprowadzenia,
   • czy jest to gramatyka jednoznaczna (podaj kontrprzykład, lub krótko uzasadnij)?
   Rozwiązanie
   
   

   $$S \to SS \to aBS \to aBAb \to aSbAb \to aAbbAb \to aabbAb \to aabbab$$

   
   

   
   

   ....

   
   

   
   zamknij

2. Podaj gramatykę bezkontekstową generującą język: $\{a^i b^{2i+1} : i \geq 0 \}$. Narysuj drzewo wyprowadzenia dla słowa aabbbbb. Rozwiązanie
   
   

   $$S \to aSbb \;\vert\;b$$

   
   

   
   

   $$\xymatrix{   & S \ar@{-}[dl] \ar@{-}[d] \ar@{-}[dr] \ar@{-}[... ... \ar@{-}[drr] & b & b\\ a & S \ar@{-}[d] & b & b\\   & b }$$

   
   

   
   zamknij

3. Podaj gramatykę bezkontekstową generującą język: $\{a^i b^{i+2\cdot j} c^j : i,j \geq 0 \}$. Narysuj drzewo wyprowadzenia dla słowa aabbbbbbbbccc. Rozwiązanie
   
   

   $$\begin{array}{rcl} S &\to& XY \\ X &\to& aXb \;\vert\;\varepsilon \\ Y &\to& bbYa \;\vert\;\varepsilon \end{array}$$

   
   

   
   

   ....

   
   

   
   zamknij

4. Dla podanej poniżej gramatyki, podaj wyprowadzenie i drzewo wyprowadzenia słowa baabab.
   
   $$\begin{eqnarray*} S & \to & AB \;\vert\;BA\\ A & \to & a \;\vert\;BBA\\ B & \to & b \;\vert\;AAB \end{eqnarray*}$$
   
   Czy podana gramatyka jest jednoznaczna (odpowiedź uzasadnij lub podaj kontrprzykład)?
5. Dla podanej poniżej gramatyki, podaj wyprowadzenie i drzewo wyprowadzenia słowa abbabbaa.
   
   $$\begin{eqnarray*} S & \to & A \;\vert\;B \;\vert\;AB\\ A & \to & BA \;\vert\;... ...\vert\;abaA \;\vert\;aa\\ B & \to & abbB \;\vert\;\varepsilon \end{eqnarray*}$$
   
   Czy podana gramatyka jest jednoznaczna (odpowiedź uzasadnij lub podaj kontrprzykład)?
6. Dla podanej poniżej gramatyki, podaj wyprowadzenie i drzewo wyprowadzenia słowa abaabb.
   
   $$\begin{eqnarray*} S&\to& aSB \;\vert\;ASb \;\vert\;ab \\ A&\to& Sa \;\vert\;bAA \;\vert\;a\\ B&\to& bS \;\vert\;BBa \;\vert\;b \end{eqnarray*}$$
   
   Czy podana gramatyka jest jednoznaczna (odpowiedź uzasadnij lub podaj kontrprzykład)?
7. Podaj gramatykę bezkontekstową generującą język:
   • $\{a^nb^{2n} : n \ge 1\}$, Rozwiązanie
     
     

     $$S \to aSbb \;\vert\;abb$$

     
     

     
     zamknij

   • $\{a^kb^n : k \ge 2n \}$, Rozwiązanie
     
     

     $$S \to aaSb \;\vert\;aS \;\vert\;\varepsilon$$

     
     

     
     zamknij

   • $\{a^kb^n : 3k \ge n \}$, Rozwiązanie
     
     

     $$S \to aSbbb \;\vert\;aSbb \;\vert\;aSb \;\vert\;aS \;\vert\;\varepsilon$$

     
     

     
     zamknij

   • $\{a^n b^k : 2n \ge 3k\}$.
   • {aⁱb^jcⁱ},
   • {aⁱb^ja^jbⁱ},
   • {aⁱbⁱa^jb^j},
   • $\{a^ib^jc^k : i + 2 \cdot j = k\}$,
   • {aⁱb^jc^k : 3i = 2j+k },
   • $\{a^nb^m : n \geq 2m \geq 0\}$,
   • $\{a^nb^mc^kd^l: n+m=k+l\}$,
   • $\{a^nb^mc^kd^l: n+l=k+m\}$,
   • $\{a^nb^mc^kd^l: n+k=m+l\}$,
   • $\{xc\;\mathord{\mbox{\rm rev}}(x) : x \in \{a,b\}^*\}$,
   • $\{xcy : x,y \in \{a,b\}^* \andalso \char93 _a(x) = \char93 _b(y)\}$,
   • $\{a^nb^mc^k: n+k=2 \cdot m\}$,
   • język złożony ze wszystkich słów nad alfabetem {a,b}^*, które nie są palindromami.
8. Rozszerz podaną w treści wykładu gramatykę wyrażeń arytmetycznych o unarny minus. Zapewnij aby była jednoznaczna. Jak silnie powinien wiązać unarny minus? Jak byś wstawił nawiasy do wyrażenia 3+3*-4*8? Zdecyduj, czy 2+-4 powinno być poprawnym wyrażeniem.
9. Rozszerz gramatykę będącą rozwiązaniem poprzedniego zadania o operację potęgowania (**). Zapewnij aby była jednoznaczna. Potęgowanie powinno wiązać mocniej niż mnożenie, ale słabiej niż unarny minus. Zdecyduj, jak byś wstawił nawiasy do wyrażenia 2**3**4 i tak też zrealizuj gramatykę.
10. Podać gramatykę generującą język złożony z takich wyrażeń arytmetycznych składających się z symboli +,*,0,1,(,), których wartość jest większa niż 2.
11. Dla zadanego automatu/wyrażenia regularnego podaj gramatyki (prawostronnie) liniowe / silnie liniowe opisujące odpowiedni język:
    • $a(a \;\vert\;b)^*aa$,
    • $(a(ab \;\vert\;ba)^*) \;\vert\;(b(bb \;\vert\;aa)^*)$,
    • 
      
      $$\begin{array}{r\vert ll} & a & b \hline \to F A & A & B \\ B & B & A \\ \end{array}$$
      
      

    • 
      
      $$\begin{array}{r\vert ll} & a & b \hline \to A & A & B \\ F B & A & C \\ F C & C & A \end{array}$$
      
      

    • 
      
      $$\begin{array}{r\vert ll} & a & b \hline \to A & B & - \\ F B & B & A \\ \end{array}$$
      
      

    • 
      
      $$\begin{array}{r\vert ll} & a & b \hline \to F A & A & B \\ B & B & C \\ C & C & A \end{array}$$
      
      

12. Podaj gramatykę wyrażeń regularnych (nad alfabetem {a,b}):
    • dowolną,
    • jednoznaczną;
    • narysuj drzewo wyprowadzenia (w jednoznacznej gramatyce) dla wyrażenia $(a \;\vert\;b^*)a^* \;\vert\;ab$.