Języki, automaty i obliczenia/Test 11: Automat ze stosem

From Studia Informatyczne

Wskaż języki bezkontekstowe, które nie są regularne:

\displaystyle L_1=\{a^kb^l: k, l \in \mathds{N}\}

\displaystyle L_2=\{a^kb^k: k \in \mathds{N}\}

\displaystyle L_3=\{a^kcb^l: k, l \in \mathds{N}\}

\displaystyle L_4=\{a^kcb^k: k \in \mathds{N}\}

\displaystyle L_5=\{w \in \{a,b\}^*: w = \overleftarrow{w}\}


Wskaż zdania prawdziwe:

Istnieje gramatyka reularna generująca język Dycka.

Język Dycka jest bezkontekstowy i nie jest regularny.

Istnieje automat skończenie stanowy rozpoznający język Łukasiewicza.

Język Łukasiewicza da się opisać wyrażeniem regularnym.

Istnieje gramatyka bezkontekstowa bez symboli bezużytecznych generująca język Dycka.


Wskaż języki, które nie są bezkontekstowe:

\displaystyle L_1=\{a^kb^l: k, l \in \mathds{N}\}

\displaystyle L_2=\{a^kb^nc^m: k < n < m\}

\displaystyle L_3=\{a^nb^n: n \in \mathds{N}\}

\displaystyle L_4=\{ca^nb^n: n \in \mathds{N}\}

\displaystyle L_5=\{w\overleftarrow{w}a^{|w|}: w \in \{a,b\}^*\}


Dana niech będzie gramatyka (\displaystyle v_0 jest symbolem początkowym):

\displaystyle \aligned v_0 &\rightarrow  v_0v_1\ |\ v_3v_1 \\ v_1 &\rightarrow  v_1v_2\ |\ v_2v_3 \\ v_2 &\rightarrow  v_4v_1\ |\ v_3v_3\ |\ a \\ v_3 &\rightarrow  v_1v_2\ |\ v_4v_2\ |\ b \\ v_4 &\rightarrow  v_3v_4\ |\ v_0v_1\ |\ c. \endaligned

Wskaż, które z poniższych słów należą do języka generowanego tą gramatyką:

\displaystyle cab^2abab

\displaystyle 1

\displaystyle b^7

\displaystyle bca

\displaystyle bcabb


Wskaż gramatyki \displaystyle G=(V, A, v_0, P) niejednoznaczne:

\displaystyle V=\{v_0,v_1,v_2,v_3\}, \displaystyle A=\{a,b\}, \displaystyle P=\{v_0 \rightarrow v_2v_1\ |\ v_3, \displaystyle v_1 \rightarrow av_1\ |\ a, \displaystyle v_2 \rightarrow v_2b\ |\ b, \displaystyle v_3 \rightarrow bv_3a\ |\ ba\}

\displaystyle V=\{v_0, v_1, v_2, v_3 \}, \displaystyle A=\{a,b\}, \displaystyle P=\{v_0 \rightarrow v_3v_1, \displaystyle v_1 \rightarrow av_1b\ |\ b, \displaystyle v_2 \rightarrow bv_2a\ |\ b, \displaystyle v_3 \rightarrow bv_2c\}

\displaystyle V=\{v_0, v_1\}, A=\{a,b\}, \displaystyle P=\{v_0 \rightarrow v_0v_1\ |\ b, \displaystyle v_1 \rightarrow av_1b\ |\ b\}

\displaystyle V=\{v_0, ..., v_5\}, \displaystyle A=\{a\}, \displaystyle P=\{v_0 \rightarrow av_1\ |\ av_3, \displaystyle v_1 \rightarrow av_2, \displaystyle v_2 \rightarrow av_1\ |\ 1, \displaystyle v_3 \rightarrow av_4, \displaystyle v_4 \rightarrow av_5, \displaystyle v_5 \rightarrow av_3\ |\ 1\}

\displaystyle V=\{v_0,v_1,v_2,v_3\}, \displaystyle A=\{a,b\}, \displaystyle P=\{v_0 \rightarrow v_2v_1, \displaystyle v_1 \rightarrow av_1\ |\ a, \displaystyle v_2 \rightarrow v_2b\ |\ b\ |\ v_3, \displaystyle v_3 \rightarrow bv_3a\ |\ ba\ |\ b \}


Gramatyka \displaystyle G=(V_N, V_T, v_0, P), gdzie \displaystyle V_N=\{v_0,..., v_5\}, \displaystyle V_T=\{a,b\}, \displaystyle P=\{v_0 \rightarrow av_1\ |\ av_3, \displaystyle v_1 \rightarrow av_2, \displaystyle v_2 \rightarrow av_1\ |\ 1, \displaystyle v_3 \rightarrow av_4, \displaystyle v_4 \rightarrow av_5, \displaystyle v_5 \rightarrow av_3\ |\ 1\}:

generuje język \displaystyle (aa)^+ +(aaa)^+

generuje język \displaystyle (aa+aaa)^+

jest równoważna gramatyce \displaystyle G'=(V_N', V_T, v_0, P'), gdzie \displaystyle V_N'=\{v_0, ..., v_6\}, \displaystyle P'=\{v_0 \rightarrow av_1, \displaystyle v_1 \rightarrow av_2, \displaystyle v_2 \rightarrow av_3\ |\ 1, \displaystyle v_3 \rightarrow av_4\ |\ 1, \displaystyle v_4 \rightarrow av_5\ |\ 1, \displaystyle v_5 \rightarrow av_6, \displaystyle v_6 \rightarrow av_1\ |\ 1

jest jednoznaczna

generuje język \displaystyle L(\mathcal{A}), gdzie \displaystyle \mathcal{A}=(S, A, s_0, f, F) jest automatem skończenie stanowym takim, że \displaystyle S=\{s_0, ..., s_4\}, \displaystyle A=\{a\}, \displaystyle F=\{s_2, s_3, s_4\}, \displaystyle f(s_0,a)=f(s_4,a)=s_1, \displaystyle f(s_1, a)=s_2, \displaystyle f(s_2, a)=s_3, \displaystyle f(s_3, a)=s_4.


Wskaż zdania prawdziwe:

każda gramatyka regularna jest jednoznaczna

każdy język jednoznaczny jest deterministyczny

każdy język regularny jest jednoznaczny

każdy język deterministyczny jest jednoznaczny

język jest jednoznaczny wtw gdy jest deterministyczny


Wskaż zdania prawdziwe:

Każda gramatyka w postaci normalnej Chomsky'ego jest bezkontekstowa.

Jeśli gramatyka bezkontekstowa \displaystyle G ma \displaystyle n produkcji, to równoważna jej gramatyka \displaystyle G' w postaci normalnej Greibach ma co najwyżej \displaystyle 2n produkcji.

Każdą gramatykę bezkontekstową można przekształcić do postaci normalnej Greibach.

Żadna gramatyka w postaci normalnej Greibach nie jest regularna.

Każda gramatyka w postaci normalnej Chomsky'ego jest właściwa.


Wskaż zdania prawdziwe:

Każdy automat ze stosem akceptujący przez pusty stos posiada równoważny automat ze stosem akceptujący przez stany końcowe.

Każdy język bezkontekstowy jest akceptowany przez pusty stos przez jednostanowy automat ze stosem.

Każdy automat ze stosem, w którym wielkość stosu jest ograniczona przez pewną stałą, jest równoważny pewnemu automatowi skończenie stanowemu.

Każdy automat ze stosem posiada równoważny deterministyczny automat ze stosem.

Każdy automat ze stosem akceptujący przez stany końcowe posiada równoważny automat ze stosem akceptujący przez pusty stos.


Rodzina języków bezkontekstowych jest zamknięta ze względu na:

homomorfizm

iloczyn mnogościowy

uzupełnienie

gwiazdkę Kleene'ego

katenację


Dane są dwie gramatyki: dla \displaystyle i=1,2\displaystyle G_i=(\{v_0,v_1,v_2\},\{a,b,c\},v_0,P_i), gdzie
\displaystyle P_1=\{v_0 \rightarrow v_1v_2,\ v_1 \rightarrow av_1b,\ v_1 \rightarrow 1,\ v_2 \rightarrow cv_2,\ v_2 \rightarrow 1\},
\displaystyle P_2 = \{v_0 \rightarrow v_1v_2,\ v_1 \rightarrow av_1,\ v_1 \rightarrow 1,\ v_2 \rightarrow bv_2c,\ v_2 \rightarrow 1\}.

Wówczas:

\displaystyle L(G_1) \cap L(G_2) \not \in \mathcal{L}_2

\displaystyle L(G_1) \cap L(G_2) jest językiem skończonym

\displaystyle L(G_1)=L(G_2)

\displaystyle L(G_1) \subset L(G_2)

\displaystyle L(G_1) \cup L(G_2)\in \mathcal{L}_2


Niech \displaystyle L będzie językiem bezkontekstowym. Wskaż problemy rozstrzygalne:

\displaystyle w \in L

\displaystyle L = \emptyset

nieskończoność \displaystyle L

równoważność dwóch gramatyk bezkontekstowych

jednoznaczność gramatyki bezkontekstowej


Niech \displaystyle L \in \mathcal{L}_2, \displaystyle R \in \mathcal{L}_3. Wówczas:

\displaystyle L \cap R \in \mathcal{L}_2

\displaystyle L \backslash R \in \mathcal{L}_2

\displaystyle \overline{L} \in \mathcal{L}_2

\displaystyle L \cap \overline{R} \in \mathcal{L}_2

\displaystyle \overline{L} \cap R \in \mathcal{L}_2


Wskaż języki deterministyczne:

\displaystyle \{a^nb^n:\ n \geq 1\} \cup \{a^nb^{3n}:\ n \geq 1\}

\displaystyle \{a^{2n}:\ n \geq 1\} \cup \{a^{3n}:\ n \geq 1\}

\displaystyle \{a^nb^{n+m}c^m:\ m,n \geq 1\}

\displaystyle \{wx\overleftarrow{w}:\ w \in \{a,b\}^*,\ x \in \{a,b\} \}

\displaystyle \{a^nb^na^mb^p:\ n,m,p \geq 1\} \cup \{a^nb^ma^pb^p:\ n,m,p \geq 1\}


Wskaż języki niejednoznaczne:

\displaystyle \{a^nb^nc^md^m:\ n,m \geq 1\} \cup \{a^nb^mc^md^n:\ n,m \geq 1\}

\displaystyle \{a^nb^mc^nd^p:\ n,m,p \geq 1\} \cup \{a^nb^mc^pd^m:\ n,m,p \geq 1\}

\displaystyle \{a^nb^na^mb^p:\ n,m,p \geq 1\} \cup \{a^nb^ma^pb^p:\ n,m,p \geq 1\}

\displaystyle \{a^nb^mc^m:\ n,m \geq 1\} \cup \{a^nb^nc^m:\ n,m \geq 1\}

\displaystyle \{a^nb^mc^md^p:\ n,m,p \geq 1\} \cup \{a^nb^mc^pd^n:\ n,m,p \geq 1\}


Automat ze stosem \displaystyle \mathcal{A}_S = (A_S, Q, \{a,b,c\}, z_0, q_0, P, Q_F), gdzie \displaystyle A_S=\{z_0,z,a,c\}, \displaystyle Q=\{q_0,q_1,q_2,q_3\}, \displaystyle Q_F=\{q_2\}, \displaystyle P = \{z_0q_0a \rightarrow z_0zq_0, \displaystyle zq_0a \rightarrow zaq_0, \displaystyle aq_0a \rightarrow a^2q_0, \displaystyle aq_0b \rightarrow a^2q_1, \displaystyle zq_0b \rightarrow zaq_1, \displaystyle aq_1b \rightarrow a^2q_1, \displaystyle aq_1c \rightarrow 1q_2, \displaystyle aq_2c \rightarrow 1q_2, \displaystyle zq_2c \rightarrow cq_3, \displaystyle cq_2c \rightarrow cq_2, \displaystyle cq_3c \rightarrow cq_2\}:

rozpoznaje język \displaystyle \{a^nb^mc^k:\ k,n,m > 0,\ k \not = n+m\}

rozpoznaje język \displaystyle \{a^nb^mc^k:\ k,n,m > 0,\ k > n+m\}

rozpoznaje język \displaystyle \{a^nb^mc^k:\ k,n,m > 0,\ k < n+m\}

jest automatem deterministycznym

rozpoznaje język \displaystyle \{a^nb^mc^k:\ k,n,m > 0,\ k = n+m\}


Niech \displaystyle L, L_1, L_2 \in \mathcal{L}_2. Wskaż problemy nierozstrzygalne w klasie \displaystyle \mathcal{L}_2:

\displaystyle w \in L

jednoznaczność \displaystyle L

\displaystyle L_1=L_2

\displaystyle L = \emptyset

nieskończoność \displaystyle L


Automat ze stosem \displaystyle \mathcal{A}_S = (A_S, Q, \{a,b\}, z_0, q_0, P, Q_F), gdzie \displaystyle A_S=\{z_0,a,b\}, \displaystyle Q=\{q_0,q_1\}, \displaystyle Q_F=\{q_0\}, \displaystyle P = \{z_0q_0a \rightarrow z_0aq_0, \displaystyle aq_0a \rightarrow aaq_0, \displaystyle aq_0b \rightarrow 1q_0, \displaystyle z_0q_0b \rightarrow z_0bq_1, \displaystyle bq_1b \rightarrow bbq_1, \displaystyle bq_1a \rightarrow 1q_1, \displaystyle z_0q_1 \rightarrow z_0q_0\}:

rozpoznaje język \displaystyle \{w \in \{a,b\}^*:\ \sharp_aw \not = \sharp_bw\}

rozpoznaje język \displaystyle \{w \in \{a,b\}^*:\ \sharp_aw \leq \sharp_bw\}

rozpoznaje język \displaystyle \{w \in \{a,b\}^*:\ \sharp_aw \geq \sharp_bw\}

jest automatem deterministycznym

rozpoznaje język \displaystyle \{w \in \{a,b\}^*:\ \sharp_aw = \sharp_bw\}


Algorytm Cocke'a-Youngera-Kasamiego:

sprawdza, czy słowo należy do języka bezkontekstowego

działa w czasie \displaystyle O(n^2\log n)

jest niedeterministyczny

może dostać na wejście dowolną gramatykę bezkontekstową

działa w oparciu o zasadę programowania dynamicznego