|
|
| Linia 6: |
Linia 6: |
|
| |
|
| ------------------------------ | | ------------------------------ |
| <quiz>
| |
| Wskaż zdania prawdziwe:
| |
|
| |
| <wrongoption>Automat liniowo ograniczony może dopisywać literę na
| |
| początku lub na końcu czytanego słowa.</wrongoption>
| |
|
| |
| <rightoption>Maszyna Turinga może zmieniać długość czytanego słowa.</rightoption>
| |
|
| |
| <wrongoption>Automat ze stosem może w jednym przejściu dowolną literę słowa zapisanego na stosie zastąpić dowolnym słowem nad alfabetem stosu.</wrongoption>
| |
|
| |
| <rightoption>Automat ze stosem i automat liniowo ograniczony mogą
| |
| zmieniać stan bez czytania litery.</rightoption>
| |
|
| |
| <wrongoption>Automat liniowo ograniczony może w czytanym słowie
| |
| zmieniać dowolną literę z alfabetu taśmy</wrongoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Wskaż zdania prawdziwe:
| |
|
| |
| <wrongoption>Każda gramatyka bezkontekstowa jest kontekstowa.</wrongoption>
| |
|
| |
| <wrongoption>Język <math>\displaystyle L</math> jest akceptowany przez deterministyczny automat ze stosem wtw gdy jest akceptowany przez niedeterministyczny automat ze stosem.</wrongoption>
| |
|
| |
| <rightoption>Każda gramatyka regularna jest bezkontekstowa.</rightoption>
| |
|
| |
| <rightoption>Każdy język bezkontekstowy jest kontekstowy.</rightoption>
| |
|
| |
| <rightoption>Język <math>\displaystyle L</math> jest akceptowany
| |
| przez deterministyczny automat skończenie stanowy wtw gdy jest akceptowany przez niedeterministyczny automat skończenie stanowy.</rightoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Rodziny <math>\displaystyle \mathcal{L}_0</math> i <math>\displaystyle \mathcal{L}_1</math> mają następujące
| |
| własności:
| |
|
| |
| <rightoption>są zamknięte na sumę</rightoption>
| |
|
| |
| <wrongoption>są zamknięte na uzupełnienie</wrongoption>
| |
|
| |
| <rightoption>są zamknięte na katenację</rightoption>
| |
|
| |
| <rightoption>są zamknięte na iloczyn mnogościowy</rightoption>
| |
|
| |
| <wrongoption>są równe</wrongoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Wskaż zdania prawdziwe:
| |
|
| |
| <rightoption>każda gramatyka kontekstowa jest rozszerzająca</rightoption>
| |
|
| |
| <wrongoption>każda gramatyka bezkontekstowa jest rozszerzająca</wrongoption>
| |
|
| |
| <wrongoption>każda gramatyka regularna jest rozszerzająca</wrongoption>
| |
|
| |
| <rightoption>dla każdej gramatyki rozszerzającej istnieje równoważna jej gramatyka kontekstowa</rightoption>
| |
|
| |
| <rightoption>dla każdej gramatyki bezkontekstowej istnieje równoważna jej gramatyka rozszerzająca</rightoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Wskaż zdania prawdziwe:
| |
|
| |
| <wrongoption>Istnieje gramatyka rozszerzająca, dla której nie istnieje równoważna jej gramatyka kontekstowa.</wrongoption>
| |
|
| |
| <rightoption>Dla dowolnej gramatyki kontekstowej z markerem końca
| |
| istnieje równoważna jej gramatyka kontekstowa.</rightoption>
| |
|
| |
| <rightoption>Dla dowolnego języka kontekstowego <math>\displaystyle L</math> istnieje automat liniowo ograniczony <math>\displaystyle \mathcal{A}_{LO}</math> taki, że <math>\displaystyle L=L(\mathcal{A}_{LO})</math>.</rightoption>
| |
|
| |
| <wrongoption>Iloczyn mnogościowy dwóch języków kontekstowych jest
| |
| językiem bezkontekstowym.</wrongoption>
| |
|
| |
| <rightoption>Dla dowolnego języka <math>\displaystyle L</math> rozpoznawanego przez automat liniowo ograniczony istnieje gramatyka <math>\displaystyle G</math> taka, że <math>\displaystyle L=L(G)</math>.</rightoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Wskaż klasy języków domknięte ze względu na iloczyn mnogościowy:
| |
|
| |
| <rightoption><math>\displaystyle \mathcal{L}_0</math></rightoption>
| |
|
| |
| <rightoption><math>\displaystyle \mathcal{L}_3</math></rightoption>
| |
|
| |
| <wrongoption><math>\displaystyle \mathcal{L}_2</math></wrongoption>
| |
|
| |
| <rightoption><math>\displaystyle \mathcal{L}_1</math></rightoption>
| |
|
| |
| <rightoption>rodzina języków akceptowanych przez automaty skończenie stanowe</rightoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Klasa <math>\displaystyle \mathcal{L}_0</math> nie jest zamknięta ze względu na:
| |
|
| |
| <wrongoption>sumę</wrongoption>
| |
|
| |
| <rightoption>uzupełnienie</rightoption>
| |
|
| |
| <wrongoption>katenację</wrongoption>
| |
|
| |
| <wrongoption>gwiazdkę Kleene'ego</wrongoption>
| |
|
| |
| <wrongoption>przecięcie</wrongoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Rozważmy język:
| |
| <center><math>\displaystyle
| |
| L=\{a^n b^n c^n\: n\geq 5\}
| |
| </math></center>
| |
|
| |
| Które z poniższych twierdzeń są prawdziwe:
| |
|
| |
| <wrongoption>problem, czy dane <math>\displaystyle w\in A^*</math> spełnia <math>\displaystyle w\in L</math> jest nierozstrzygalny</wrongoption>
| |
|
| |
| <rightoption><math>\displaystyle L\in \textbf{PSPACE}</math></rightoption>
| |
|
| |
| <rightoption><math>\displaystyle L\in \textbf{NP}</math></rightoption>
| |
|
| |
| <wrongoption>maszyna Turinga rozpoznająca język <math>\displaystyle L</math> musi być niedeterministyczna lub posiadać <math>\displaystyle 5</math> taśm</wrongoption>
| |
|
| |
| <rightoption><math>\displaystyle L\in \textbf{P}</math></rightoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Gramatyki typu '''(0)''' generują klasę języków:
| |
|
| |
| <wrongoption>rekurencyjnych, ale tylko przy założeniu tezy Churcha</wrongoption>
| |
|
| |
| <wrongoption>zawierającą klasę języków rekurencyjnie przeliczalnych, a przy dodatkowym założeniu tezy Churcha, także klasę języków rekurencyjnych</wrongoption>
| |
|
| |
| <wrongoption>identyczną z klasą języków rozpoznawalnych przez automat liniowo ograniczony</wrongoption>
| |
|
| |
| <rightoption>przy założeniu tezy Churcha, identyczną z klasą języków rozpoznawanych przez deterministyczną maszynę Turinga</rightoption>
| |
|
| |
| <wrongoption>zawierającą wszystkie języki które są rozpoznawane przez deterministyczną maszynę Turinga, ale istotnie
| |
| węższą niż klasa języków rozpoznawalnych przez niedeterministyczne maszyny Turinga.</wrongoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Załóżmy, że <math>\displaystyle L_1 \propto L_2</math> oraz dodatkowo <math>\displaystyle L_1 \in
| |
| \textbf{NP}</math>. W tej sytuacji:
| |
|
| |
| <wrongoption>wprost z definicji transformacji <math>\displaystyle \propto</math> wynika, że <math>\displaystyle L_2 \in </math> '''NP''' </wrongoption>
| |
|
| |
| <rightoption><math>\displaystyle L_1 \in </math> '''PSPACE''' </rightoption>
| |
|
| |
| <rightoption>jeśli dodatkowo <math>\displaystyle L_1 \not\in \textbf{P}</math> to <math>\displaystyle L_2 \not\in \textbf{P}</math></rightoption>
| |
|
| |
| <rightoption>jeśli język <math>\displaystyle L_1</math> jest <math>\displaystyle \textbf{P}</math>-zupełny, to <math>\displaystyle L_2</math> jest <math>\displaystyle \textbf{P}</math>-trudny</rightoption>
| |
|
| |
| <wrongoption>wykluczony jest warunek <math>\displaystyle L_2 \in \textbf{PSPACE}</math></wrongoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Które z poniżej wymienionych problemów są nierozstrzygalne:
| |
|
| |
| <rightoption>problem niejednoznaczności dla gramatyk bezkontekstowych</rightoption>
| |
|
| |
| <wrongoption>problem, czy <math>\displaystyle L_1\cap L_2\neq \emptyset</math> dla języków regularnych</wrongoption>
| |
|
| |
| <rightoption>problem, czy dana gramatyka typu '''(0)''' generuje język pusty</rightoption>
| |
|
| |
| <wrongoption>problem Posta nad alfabetem <math>\displaystyle A=\{1,2,\dots,n\}</math> gdzie <math>\displaystyle n\geq 1</math>.</wrongoption>
| |
|
| |
| <rightoption>problem, czy <math>\displaystyle L_1 \subset L_2</math> dla języków zadanych przez gramatyki kontekstowe</rightoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Które z poniższych maszyn są równoważne maszynie Turinga?
| |
|
| |
| <rightoption>maszyna Turinga z wieloma taśmami</rightoption>
| |
|
| |
| <rightoption>maszyna Turinga z wieloma głowicami</rightoption>
| |
|
| |
| <rightoption>maszyna Turinga z taśmą jednostronnie nieskończoną</rightoption>
| |
|
| |
| <wrongoption>maszyna Turinga z wieloma taśmami, z których każda jest obustronnie ograniczona</wrongoption>
| |
|
| |
| <rightoption>maszyna Turinga niedeterministyczna</rightoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Stwierdzenie mówiące, iż każda efektywna procedura (algorytm) da się
| |
| opisać przez pewną maszynę Turinga, znane jest jako:
| |
|
| |
| <wrongoption>twierdzenie Kleene'ego</wrongoption>
| |
|
| |
| <wrongoption>twierdzenie Nerode'a</wrongoption>
| |
|
| |
| <rightoption>teza Churcha</rightoption>
| |
|
| |
| <wrongoption>twierdzenie Savitcha</wrongoption>
| |
|
| |
| <wrongoption>problem '''P'''<nowiki> =</nowiki> '''NP'''</wrongoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
|
| |
| 111111111111111111111111111111111111111111111111111111111111111
| |
|
| |
| <quiz>
| |
| Wskaż języki bezkontekstowe, które nie są regularne:
| |
|
| |
| <wrongoption><math>\displaystyle L_1=\{a^kb^l: k, l \in \mathds{N}\}</math></wrongoption>
| |
|
| |
| <rightoption><math>\displaystyle L_2=\{a^kb^k: k \in \mathds{N}\}</math></rightoption>
| |
|
| |
| <wrongoption><math>\displaystyle L_3=\{a^kcb^l: k, l \in \mathds{N}\}</math></wrongoption>
| |
|
| |
| <rightoption><math>\displaystyle L_4=\{a^kcb^k: k \in \mathds{N}\}</math></rightoption>
| |
|
| |
| <rightoption><math>\displaystyle L_5=\{w \in \{a,b\}^*: w = \overleftarrow{w}\}</math></rightoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Wskaż zdania prawdziwe:
| |
|
| |
| <wrongoption>Istnieje gramatyka reularna generująca język Dycka.</wrongoption>
| |
|
| |
| <rightoption>Język Dycka jest bezkontekstowy i nie jest regularny.</rightoption>
| |
|
| |
| <wrongoption>Istnieje automat skończenie stanowy rozpoznający język Łukasiewicza.</wrongoption>
| |
|
| |
| <wrongoption>Język Łukasiewicza da się opisać wyrażeniem regularnym.</wrongoption>
| |
|
| |
| <rightoption>Istnieje gramatyka bezkontekstowa bez symboli bezużytecznych generująca język Dycka.</rightoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Wskaż języki, które nie są bezkontekstowe:
| |
|
| |
| <wrongoption><math>\displaystyle L_1=\{a^kb^l: k, l \in \mathds{N}\}</math></wrongoption>
| |
|
| |
| <rightoption><math>\displaystyle L_2=\{a^kb^nc^m: k < n < m\}</math></rightoption>
| |
|
| |
| <wrongoption><math>\displaystyle L_3=\{a^nb^n: n \in \mathds{N}\}</math></wrongoption>
| |
|
| |
| <wrongoption><math>\displaystyle L_4=\{ca^nb^n: n \in \mathds{N}\}</math></wrongoption>
| |
|
| |
| <wrongoption><math>\displaystyle L_5=\{w\overleftarrow{w}a^{|w|}: w \in \{a,b\}^*\}</math></wrongoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Dana niech będzie gramatyka (<math>\displaystyle v_0</math> jest symbolem początkowym):
| |
|
| |
| <center><math>\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</math></center>
| |
|
| |
| Wskaż, które z poniższych słów należą do języka generowanego tą
| |
| gramatyką:
| |
|
| |
| <rightoption><math>\displaystyle cab^2abab</math></rightoption>
| |
|
| |
| <wrongoption><math>\displaystyle 1</math></wrongoption>
| |
|
| |
| <rightoption><math>\displaystyle b^7</math></rightoption>
| |
|
| |
| <wrongoption><math>\displaystyle bca</math></wrongoption>
| |
|
| |
| <rightoption><math>\displaystyle bcabb</math></rightoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Wskaż gramatyki <math>\displaystyle G=(V, A, v_0, P)</math> niejednoznaczne:
| |
|
| |
| <rightoption><math>\displaystyle V=\{v_0,v_1,v_2,v_3\}</math>, <math>\displaystyle A=\{a,b\}</math>, <math>\displaystyle P=\{v_0 \rightarrow
| |
| v_2v_1\ |\ v_3</math>, <math>\displaystyle v_1 \rightarrow av_1\ |\ a</math>, <math>\displaystyle v_2 \rightarrow
| |
| v_2b\ |\ b</math>, <math>\displaystyle v_3 \rightarrow bv_3a\ |\ ba\}</math></rightoption>
| |
|
| |
| <wrongoption><math>\displaystyle V=\{v_0, v_1, v_2, v_3 \}</math>, <math>\displaystyle A=\{a,b\}</math>, <math>\displaystyle P=\{v_0 \rightarrow
| |
| v_3v_1</math>, <math>\displaystyle v_1 \rightarrow av_1b\ |\ b</math>, <math>\displaystyle v_2 \rightarrow bv_2a\ |\
| |
| b</math>, <math>\displaystyle v_3 \rightarrow bv_2c\}</math></wrongoption>
| |
|
| |
| <wrongoption><math>\displaystyle V=\{v_0, v_1\}, A=\{a,b\}</math>, <math>\displaystyle P=\{v_0 \rightarrow v_0v_1\
| |
| |\ b</math>, <math>\displaystyle v_1 \rightarrow av_1b\ |\ b\}</math></wrongoption>
| |
|
| |
| <rightoption><math>\displaystyle V=\{v_0, ..., v_5\}</math>, <math>\displaystyle A=\{a\}</math>, <math>\displaystyle P=\{v_0 \rightarrow
| |
| av_1\ |\ av_3</math>, <math>\displaystyle v_1 \rightarrow av_2</math>, <math>\displaystyle v_2 \rightarrow av_1\ |\
| |
| 1</math>, <math>\displaystyle v_3 \rightarrow av_4</math>, <math>\displaystyle v_4 \rightarrow av_5</math>, <math>\displaystyle v_5 \rightarrow
| |
| av_3\ |\ 1\}</math></rightoption>
| |
|
| |
| <rightoption><math>\displaystyle V=\{v_0,v_1,v_2,v_3\}</math>, <math>\displaystyle A=\{a,b\}</math>, <math>\displaystyle P=\{v_0 \rightarrow
| |
| v_2v_1</math>, <math>\displaystyle v_1 \rightarrow av_1\ |\ a</math>, <math>\displaystyle v_2 \rightarrow v_2b\ |\
| |
| b\ |\ v_3</math>, <math>\displaystyle v_3 \rightarrow bv_3a\ |\ ba\ |\ b \}</math></rightoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Gramatyka <math>\displaystyle G=(V_N, V_T, v_0, P)</math>, gdzie <math>\displaystyle V_N=\{v_0,..., v_5\}</math>,
| |
| <math>\displaystyle V_T=\{a,b\}</math>, <math>\displaystyle P=\{v_0 \rightarrow av_1\ |\ av_3</math>, <math>\displaystyle v_1
| |
| \rightarrow av_2</math>, <math>\displaystyle v_2 \rightarrow av_1\ |\ 1</math>, <math>\displaystyle v_3 \rightarrow
| |
| av_4</math>, <math>\displaystyle v_4 \rightarrow av_5</math>, <math>\displaystyle v_5 \rightarrow av_3\ |\ 1\}</math>:
| |
|
| |
| <rightoption>generuje język <math>\displaystyle (aa)^+(aaa)^+</math></rightoption>
| |
|
| |
| <wrongoption>generuje język <math>\displaystyle (aa+aaa)^*</math></wrongoption>
| |
|
| |
| <rightoption>jest równoważna gramatyce <math>\displaystyle G'=(V_N', V_T, v_0, P')</math>, gdzie
| |
| <math>\displaystyle V_N'=\{v_0, ..., v_6\}</math>, <math>\displaystyle P'=\{v_0 \rightarrow av_1</math>, <math>\displaystyle v_1
| |
| \rightarrow av_2</math>, <math>\displaystyle v_2 \rightarrow av_3\ |\ 1</math>, <math>\displaystyle v_3 \rightarrow
| |
| av_4\ |\ 1</math>, <math>\displaystyle v_4 \rightarrow av_5\ |\ 1</math>, <math>\displaystyle v_5 \rightarrow av_6</math>,
| |
| <math>\displaystyle v_6 \rightarrow av_1\ |\ 1</math></rightoption>
| |
|
| |
| <wrongoption>jest jednoznaczna</wrongoption>
| |
|
| |
| <wrongoption>generuje język <math>\displaystyle L(\mathcal{A})</math>, gdzie <math>\displaystyle \mathcal{A}=(S, A,
| |
| s_0, f, F)</math> jest automatem skończenie stanowym takim, że <math>\displaystyle S=\{s_0,
| |
| ..., s_4\}</math>, <math>\displaystyle A=\{a\}</math>, <math>\displaystyle F=\{s_2, s_3, s_4\}</math>,
| |
| <math>\displaystyle f(s_0,a)=f(s_4,a)=s_1</math>, <math>\displaystyle f(s_1, a)=s_2</math>, <math>\displaystyle f(s_2, a)=s_3</math>, <math>\displaystyle f(s_3,
| |
| a)=s_4</math>.</wrongoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Wskaż zdania prawdziwe:
| |
|
| |
| <wrongoption>każda gramatyka regularna jest jednoznaczna</wrongoption>
| |
|
| |
| <wrongoption>każdy język jednoznaczny jest deterministyczny</wrongoption>
| |
|
| |
| <rightoption>każdy język regularny jest jednoznaczny</rightoption>
| |
|
| |
| <rightoption>każdy język deterministyczny jest jednoznaczny</rightoption>
| |
|
| |
| <wrongoption>język jest jednoznaczny wtw gdy jest deterministyczny</wrongoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Wskaż zdania prawdziwe:
| |
|
| |
| <rightoption>Każda gramatyka w postaci normalnej Chomsky'ego jest bezkontekstowa.</rightoption>
| |
|
| |
| <wrongoption>Jeśli gramatyka bezkontekstowa <math>\displaystyle G</math> ma <math>\displaystyle n</math> produkcji, to równoważna jej gramatyka <math>\displaystyle G'</math> w postaci normalnej Greibach ma co najwyżej <math>\displaystyle 2n</math> produkcji.</wrongoption>
| |
|
| |
| <wrongoption>Każdą gramatykę bezkontekstową można przekształcić do postaci normalnej Greibach.</wrongoption>
| |
|
| |
| <wrongoption>Żadna gramatyka w postaci normalnej Greibach nie jest regularna.</wrongoption>
| |
|
| |
| <rightoption>Każda gramatyka w postaci normalnej Chomsky'ego jest
| |
| właściwa.</rightoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Wskaż zdania prawdziwe:
| |
|
| |
| <rightoption>Każdy automat ze stosem akceptujący przez pusty stos
| |
| posiada równoważny automat ze stosem akceptujący przez stany
| |
| końcowe.</rightoption>
| |
|
| |
| <rightoption>Każdy język bezkontekstowy jest akceptowany przez pusty stos przez jednostanowy automat ze stosem.</rightoption>
| |
|
| |
| <rightoption>Każdy automat ze stosem, w którym wielkość stosu jest ograniczona przez pewną stałą, jest równoważny pewnemu automatowi skończenie stanowemu.</rightoption>
| |
|
| |
| <wrongoption>Każdy automat ze stosem posiada równoważny deterministyczny automat ze stosem.</wrongoption>
| |
|
| |
| <rightoption>Każdy automat ze stosem akceptujący przez stany końcowe posiada równoważny automat ze stosem akceptujący przez pusty stos.</rightoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Rodzina języków bezkontekstowych jest zamknięta ze względu na:
| |
|
| |
| <rightoption>homomorfizm</rightoption>
| |
|
| |
| <wrongoption>iloczyn mnogościowy</wrongoption>
| |
|
| |
| <wrongoption>uzupełnienie</wrongoption>
| |
|
| |
| <rightoption>gwiazdkę Kleene'ego</rightoption>
| |
|
| |
| <rightoption>katenację</rightoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Dane są dwie gramatyki: dla <math>\displaystyle i=1,2\displaystyle G_i=(\{v_0,v_1,v_2\},\{a,b,c\},v_0,P_i)</math>, gdzie <center><math>\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\},</math></center>
| |
| <center><math>\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\}.</math></center>
| |
| Wówczas:
| |
|
| |
| <rightoption><math>\displaystyle L(G_1) \cap L(G_2) \not \in \mathcal{L}_2</math></rightoption>
| |
|
| |
| <wrongoption><math>\displaystyle L(G_1) \cap L(G_2)</math> jest językiem skończonym</wrongoption>
| |
|
| |
| <wrongoption><math>\displaystyle L(G_1)=L(G_2)</math></wrongoption>
| |
|
| |
| <wrongoption><math>\displaystyle L(G_1) \subset L(G_2)</math></wrongoption>
| |
|
| |
| <rightoption><math>\displaystyle L(G_1) \cup L(G_2)\in \mathcal{L}_2</math></rightoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Niech <math>\displaystyle L</math> będzie językiem bezkontekstowym. Wskaż problemy rozstrzygalne:
| |
|
| |
| <rightoption><math>\displaystyle w \in L</math></rightoption>
| |
|
| |
| <rightoption><math>\displaystyle L = \emptyset</math></rightoption>
| |
|
| |
| <rightoption>nieskończoność <math>\displaystyle L</math></rightoption>
| |
|
| |
| <wrongoption>równoważność dwóch gramatyk bezkontekstowych</wrongoption>
| |
|
| |
| <wrongoption>jednoznaczność gramatyki bezkontekstowej</wrongoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Niech <math>\displaystyle L \in \mathcal{L}_2</math>, <math>\displaystyle R \in \mathcal{L}_3</math>. Wówczas:
| |
|
| |
| <rightoption><math>\displaystyle L \cap R \in \mathcal{L}_2</math></rightoption>
| |
|
| |
| <rightoption><math>\displaystyle L \backslash R \in \mathcal{L}_2</math></rightoption>
| |
|
| |
| <wrongoption><math>\displaystyle \overline{L} \in \mathcal{L}_2</math></wrongoption>
| |
|
| |
| <rightoption><math>\displaystyle L \cap \overline{R} \in \mathcal{L}_2</math></rightoption>
| |
|
| |
| <wrongoption><math>\displaystyle \overline{L} \cap R \in \mathcal{L}_2</math></wrongoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Wskaż języki deterministyczne:
| |
|
| |
| <wrongoption><math>\displaystyle \{a^nb^n:\ n \geq 1\} \cup \{a^nb^{3n}:\ n \geq 1\}</math></wrongoption>
| |
|
| |
| <rightoption><math>\displaystyle \{a^{2n}:\ n \geq 1\} \cup \{a^{3n}:\ n \geq 1\}</math></rightoption>
| |
|
| |
| <rightoption><math>\displaystyle \{a^nb^{n+m}c^m:\ m,n \geq 1\}</math></rightoption>
| |
|
| |
| <wrongoption><math>\displaystyle \{wx\overleftarrow{w}:\ w \in \{a,b\}^*,\ x \in \{a,b\}
| |
| \}</math></wrongoption>
| |
|
| |
| <rightoption><math>\displaystyle \{a^nb^na^mb^p:\ n,m,p \geq 1\} \cup \{a^nb^ma^pb^p:\
| |
| n,m,p \geq 1\}</math></rightoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Wskaż języki niejednoznaczne:
| |
|
| |
| <rightoption><math>\displaystyle \{a^nb^nc^md^m:\ n,m \geq 1\} \cup \{a^nb^mc^md^n:\ n,m
| |
| \geq 1\}</math></rightoption>
| |
|
| |
| <rightoption><math>\displaystyle \{a^nb^mc^nd^p:\ n,m,p \geq 1\} \cup \{a^nb^mc^pd^m:\
| |
| n,m,p \geq 1\}</math></rightoption>
| |
|
| |
| <wrongoption><math>\displaystyle \{a^nb^na^mb^p:\ n,m,p \geq 1\} \cup \{a^nb^ma^pb^p:\
| |
| n,m,p \geq 1\}</math></wrongoption>
| |
|
| |
| <rightoption><math>\displaystyle \{a^nb^mc^m:\ n,m \geq 1\} \cup \{a^nb^nc^m:\ n,m \geq
| |
| 1\}</math></rightoption>
| |
|
| |
| <wrongoption><math>\displaystyle \{a^nb^mc^md^p:\ n,m,p \geq 1\} \cup \{a^nb^mc^pd^n:\
| |
| n,m,p \geq 1\}</math></wrongoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Automat ze stosem <math>\displaystyle \mathcal{A}_S = (A_S, Q, \{a,b,c\}, z_0, q_0, P,
| |
| Q_F)</math>, gdzie <math>\displaystyle A_S=\{z_0,z,a,c\}</math>, <math>\displaystyle Q=\{q_0,q_1,q_2,q_3\}</math>,
| |
| <math>\displaystyle Q_F=\{q_2\}</math>, <math>\displaystyle P = \{z_0q_0a \rightarrow z_0zq_0</math>, <math>\displaystyle zq_0a
| |
| \rightarrow zaq_0</math>, <math>\displaystyle aq_0a \rightarrow a^2q_0</math>, <math>\displaystyle aq_0b \rightarrow
| |
| a^2q_1</math>, <math>\displaystyle zq_0b \rightarrow zaq_1</math>, <math>\displaystyle aq_1b \rightarrow a^2q_1</math>,
| |
| <math>\displaystyle aq_1c \rightarrow 1q_2</math>, <math>\displaystyle aq_2c \rightarrow 1q_2</math>, <math>\displaystyle zq_2c
| |
| \rightarrow cq_3</math>, <math>\displaystyle cq_2c \rightarrow cq_2</math>, <math>\displaystyle cq_3c \rightarrow
| |
| cq_2\}</math>:
| |
|
| |
| <rightoption>rozpoznaje język <math>\displaystyle \{a^nb^mc^k:\ k,n,m > 0,\ k \not = n+m\}</math></rightoption>
| |
|
| |
| <wrongoption>rozpoznaje język <math>\displaystyle \{a^nb^mc^k:\ k,n,m > 0,\ k > n+m\}</math></wrongoption>
| |
|
| |
| <wrongoption>rozpoznaje język <math>\displaystyle \{a^nb^mc^k:\ k,n,m > 0,\ k < n+m\}</math></wrongoption>
| |
|
| |
| <rightoption>jest automatem deterministycznym</rightoption>
| |
|
| |
| <wrongoption>rozpoznaje język <math>\displaystyle \{a^nb^mc^k:\ k,n,m > 0,\ k = n+m\}</math></wrongoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Niech <math>\displaystyle L, L_1, L_2 \in \mathcal{L}_2</math>. Wskaż problemy
| |
| nierozstrzygalne w klasie <math>\displaystyle \mathcal{L}_2</math>:
| |
|
| |
| <wrongoption><math>\displaystyle w \in L</math></wrongoption>
| |
|
| |
| <rightoption>jednoznaczność <math>\displaystyle L</math></rightoption>
| |
|
| |
| <rightoption><math>\displaystyle L_1=L_2</math></rightoption>
| |
|
| |
| <wrongoption><math>\displaystyle L = \emptyset</math></wrongoption>
| |
|
| |
| <wrongoption>nieskończoność <math>\displaystyle L</math></wrongoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Automat ze stosem <math>\displaystyle \mathcal{A}_S = (A_S, Q, \{a,b\}, z_0, q_0, P,
| |
| Q_F)</math>, gdzie <math>\displaystyle A_S=\{z_0,a,b\}</math>, <math>\displaystyle Q=\{q_0,q_1\}</math>, <math>\displaystyle Q_F=\{q_0\}</math>, <math>\displaystyle P =
| |
| \{z_0q_0a \rightarrow z_0aq_0</math>, <math>\displaystyle aq_0a \rightarrow aaq_0</math>, <math>\displaystyle aq_0b
| |
| \rightarrow 1q_0</math>, <math>\displaystyle z_0q_0b \rightarrow z_0bq_1</math>, <math>\displaystyle bq_1b \rightarrow
| |
| bbq_1</math>, <math>\displaystyle bq_1a \rightarrow 1q_1</math>, <math>\displaystyle z_0q_1 \rightarrow z_0q_0\}</math>:
| |
|
| |
| <wrongoption>rozpoznaje język <math>\displaystyle \{w \in \{a,b\}^*:\ \sharp_aw \not = \sharp_bw\}</math></wrongoption>
| |
|
| |
| <wrongoption>rozpoznaje język <math>\displaystyle \{w \in \{a,b\}^*:\ \sharp_aw \leq \sharp_bw\}</math></wrongoption>
| |
|
| |
| <rightoption>rozpoznaje język <math>\displaystyle \{w \in \{a,b\}^*:\ \sharp_aw \geq \sharp_bw\}</math></rightoption>
| |
|
| |
| <rightoption>jest automatem deterministycznym</rightoption>
| |
|
| |
| <wrongoption>rozpoznaje język <math>\displaystyle \{w \in \{a,b\}^*:\ \sharp_aw = \sharp_bw\}</math></wrongoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Algorytm Cocke'a-Youngera-Kasamiego:
| |
|
| |
| <rightoption>sprawdza, czy słowo należy do języka bezkontekstowego</rightoption>
| |
|
| |
| <wrongoption>działa w czasie <math>\displaystyle O(n^2\log n)</math></wrongoption>
| |
|
| |
| <wrongoption>jest niedeterministyczny</wrongoption>
| |
|
| |
| <wrongoption>może dostać na wejście dowolną gramatykę bezkontekstową</wrongoption>
| |
|
| |
| <rightoption>działa w oparciu o zasadę programowania dynamicznego</rightoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
| 8888888888888888888888888888888888888888888888888888888888
| |
| <quiz>
| |
| Wskaż, które z poniższych struktur są monoidami:
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle (\mathds{Z}_{mod\ 2}, \cdot)</math></rightoption>
| |
| <wrongoption reply="Źle"><math>\displaystyle (\mathds{N}_1, +)</math>, gdzie <math>\displaystyle \mathds{N}_1=\{1,2,3,...\}</math></wrongoption>
| |
| <wrongoption reply="Źle"><math>\displaystyle (\mathds{N}_p,+)</math>, gdzie <math>\displaystyle \mathds{N}_p</math> jest zbiorem wszystkich liczb pierwszych</wrongoption>
| |
| <rightoption reply="Dobrze"><math>\displaystyle (\mathds{R}, \cdot)</math></rightoption>
| |
| <rightoption reply="Dobrze"><math>\displaystyle (\mathds{Z}, +)</math></rightoption>
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Wskaż stwierdzenia prawdziwe:
| |
|
| |
| <wrongoption reply="Źle"><math>\displaystyle abbaaa \in \{aa,bb\}^*</math></wrongoption>
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle abbaaa \in \{a,b\}^*</math></rightoption>
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle abbaaa \in \{abb,a\}^*</math></rightoption>
| |
|
| |
| <wrongoption reply="Źle"><math>\displaystyle abbaaa \in \{ba, ab\}^*</math></wrongoption>
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle abbaaa \in \{aa, ab, ba\}^*</math></rightoption>
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Wskaż, które z poniższych odwzorowań są homomorfizmami:
| |
|
| |
| <wrongoption reply="Źle"><math>\displaystyle h: (\mathds{R},+) \rightarrow (\mathds{Z},+)</math>, <math>\displaystyle h(x)=3x</math></wrongoption>
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle h: (\mathds{R},+) \rightarrow (\mathds{R},+)</math>, <math>\displaystyle h(x)=3x</math></rightoption>
| |
|
| |
| <wrongoption reply="Źle"><math>\displaystyle h: (\mathds{R}, \cdot) \rightarrow (\mathds{R}, \cdot)</math>,
| |
| <math>\displaystyle h(x)=3x</math></wrongoption>
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle h: \{a,b\}^* \rightarrow \{a,b\}^*</math>, <math>\displaystyle h(a)=a^2</math>,
| |
| <math>\displaystyle h(b)=ab^2</math></rightoption>
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle h: \{a,b\}^* \rightarrow (\mathds{Z},+)</math>, <math>\displaystyle h(a)=1</math>, <math>\displaystyle h(b)=1</math></rightoption>
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Dany niech będzie system przepisujący <math>\displaystyle RS=(\{a,b,c\},
| |
| \{(a,b),(b,c),(b,a),(cc,b))</math> oraz niech <math>\displaystyle I=\{ccb\}</math>. Wskaż
| |
| stwierdzenia prawdziwe:
| |
|
| |
| <wrongoption reply="Źle"><math>\displaystyle abc \in L_{gen}(RS, I)</math></wrongoption>
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle ccb \in L_{gen}(RS, I)</math> </rightoption>
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle bb \in L_{gen}(RS, I)</math></rightoption>
| |
|
| |
| <wrongoption reply="Źle"><math>\displaystyle aab \in L_{gen}(RS, I)</math></wrongoption>
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle aa \in L_{gen}(RS, I)</math></rightoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Wyrażenie regularne
| |
| <center><math>\displaystyle ((aa+bb)^*(ab+ba)(aa+bb)^*(ab+ba))^*(aa+bb)^*</math></center>
| |
| reprezentuje język:
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle \{w \in \{a,b\}^*:\ \sharp_aw = 2k</math>, <math>\displaystyle \sharp_bw = 2l</math>,
| |
| <math>\displaystyle k,l >0\}</math></rightoption>
| |
|
| |
| <wrongoption reply="Źle"><math>\displaystyle \{w \in \{a,b\}^*:\ \sharp_aw - \sharp_bw = 0 (mod 2)\}</math></wrongoption>
| |
|
| |
| <wrongoption reply="Źle"><math>\displaystyle \{w \in \{a,b\}^*:\ \sharp_aw = \sharp_bw = 2k, k \geq
| |
| 0\}</math></wrongoption>
| |
|
| |
| <wrongoption reply="Źle"><math>\displaystyle \{w \in \{a,b\}^*:\ \sharp_aw - \sharp_bw = 1 (mod 2)\}</math></wrongoption>
| |
|
| |
| <wrongoption reply="Źle"><math>\displaystyle \{w \in \{a,b\}^*: \sharp_aw = 4k</math>, <math>\displaystyle \sharp_bw = 4l</math>, <math>\displaystyle k,
| |
| l \geq 0\}</math></wrongoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
|
| |
| Niech <math>\displaystyle A=\{a,b\}</math> oraz <math>\displaystyle L=aA^*a</math>. Wskaż zdania prawdziwe:
| |
|
| |
| <wrongoption reply="Źle">minimalny automat akceptujący <math>\displaystyle L</math> ma 5 stanów</wrongoption>
| |
|
| |
| <rightoption reply="Dobrze">ilość klas równoważności prawej kongruencji syntaktycznej
| |
| <math>\displaystyle P_L^r</math> wyznaczonej przez <math>\displaystyle L</math> jest równa 4</rightoption>
| |
|
| |
| <wrongoption reply="Źle"><math>\displaystyle A^* \backslash L = bA^*b + b</math></wrongoption>
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle A^* \backslash L = bA^*+aA^*b+a+1</math></rightoption>
| |
|
| |
| <rightoption reply="Dobrze">monoid przejśc minimalnego automatu akceptującego <math>\displaystyle L</math> ma 6
| |
| elementów</rightoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
|
| |
| Niech <math>\displaystyle L</math> będzie dowolnym językiem regularnym. Wskaż zdania prawdziwe:
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle L</math> jest rozpoznawany przez pewien niedeterministyczny automat skończenie stanowy z pustymi przejściami</rightoption>
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle L</math> jest rozpoznawany przez automat deterministyczny
| |
| skończenie stanowy</rightoption>
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle L</math> jest rozpoznawany przez niedeterministyczny automat z pustymi przejściami o jednoelementowym zbiorze stanów początkowych</rightoption>
| |
|
| |
| <wrongoption reply="Źle">Nie istnieje automat niedeterministyczny z pustymi przejściami rozpoznający <math>\displaystyle L</math> i taki, że zbiór stanów początkowych jest jednoelementowy</wrongoption>
| |
|
| |
| <wrongoption reply="Źle">Nie istnieje gramatyka lewoliniowa generująca <math>\displaystyle L</math></wrongoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
|
| |
| Niech <math>\displaystyle L_1</math>, <math>\displaystyle L_2</math> będą językami rozpoznawanymi odpowiednio przez
| |
| automaty o <math>\displaystyle n_1</math> i <math>\displaystyle n_2</math> stanach. Aby stwierdzić, dla dowolnego
| |
| słowa <math>\displaystyle w</math>, czy jest ono rozpoznawane przez oba automaty, wystarczy
| |
| skonstruować odpowiedni automat mający
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle n_1 \cdot n_2</math> stanów</rightoption>
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle O(n_1+n_2)</math> stanów</rightoption>
| |
|
| |
| <wrongoption reply="Źle"><math>\displaystyle n_1</math> stanów</wrongoption>
| |
|
| |
| <wrongoption reply="Źle"><math>\displaystyle n_2</math> stanów</wrongoption>
| |
|
| |
| <wrongoption reply="Źle">3 stany</wrongoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
|
| |
| Język <math>\displaystyle L</math> składa się ze wszystkich słów nad alfabetem <math>\displaystyle A=\{a,b\}</math>
| |
| nie zawierających podsłowa <math>\displaystyle a^3</math>. Wskaż wyrażenie regularne
| |
| reprezentujące <math>\displaystyle L</math>:
| |
|
| |
| <wrongoption reply="Źle"><math>\displaystyle (b^*(1+a+aa)b^*)^*</math></wrongoption>
| |
|
| |
| <wrongoption reply="Źle"><math>\displaystyle (b^*(1+a+aa)bb^*)^*</math></wrongoption>
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle (b+ab+aab)^*+(b+ab+aab)^*a+(b+ab+aab)^*aa</math></rightoption>
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle ((1+a+aa)bb^*)^*(1+a+aa)</math></rightoption>
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle b^*(a+aa)bb^*)^*(1+a+aa)</math></rightoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
|
| |
| Wskaż warunki równoważne temu, by język <math>\displaystyle L</math> był akceptowany przez
| |
| automat skończenie stanowy:
| |
|
| |
| <wrongoption reply="Źle">Istnieje liczba naturalna <math>\displaystyle N \geq 1</math> taka, że każde słowo
| |
| <math>\displaystyle w \in L</math> o długości <math>\displaystyle |w| \geq N</math> można przedstawić jako katenację
| |
| <math>\displaystyle w = v_1uv_2</math>, gdzie <math>\displaystyle v_1, v_2 \in A^*</math>, <math>\displaystyle u \in A^+</math> oraz <math>\displaystyle v_1u^*v_2
| |
| \subset L</math>.</wrongoption>
| |
|
| |
| <rightoption reply="Dobrze">Istnieje skończony monoid <math>\displaystyle M</math> i homomorfizm <math>\displaystyle \phi: A^*
| |
| \rightarrow M</math> taki, że <math>\displaystyle \phi^{-1}(\phi(L)) = L</math>.</rightoption>
| |
|
| |
| <wrongoption reply="Źle"><math>\displaystyle L</math> jest sumą wybranych klas równoważności pewnej
| |
| kongruencji <math>\displaystyle \rho</math> na <math>\displaystyle A^*</math>: <center><math>\displaystyle L = \cup_{w \in L}[w]_\rho.</math></center></wrongoption>
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle L \in \mathcal{REG}(A^*)</math>.</rightoption>
| |
|
| |
| <wrongoption reply="Źle"><math>\displaystyle L</math> jest akceptowany przez deterministyczny automat
| |
| skończenie stanowy z jednym stanem końcowym.</wrongoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Automat <math>\displaystyle \mathcal{A}=(S, A, s_0, f, F)</math>, gdzie <math>\displaystyle S=\{s_0, s_1, s_2,
| |
| s_3\}</math>, <math>\displaystyle A=\{a,b\}</math>, <math>\displaystyle F=\{s_1\}</math>,
| |
|
| |
| <center>
| |
| {| border=1
| |
| |+ <span style="font-variant:small-caps"></span>
| |
| |-
| |
| | <math>\displaystyle f</math> || <math>\displaystyle s_0</math> || <math>\displaystyle s_1</math> || <math>\displaystyle s_2</math> ||
| |
| <math>\displaystyle s_3</math>
| |
| |-
| |
| | <math>\displaystyle a</math> || <math>\displaystyle s_1</math> || <math>\displaystyle s_0</math> || <math>\displaystyle s_3</math> || <math>\displaystyle s_2</math>
| |
| |-
| |
| | <math>\displaystyle b</math> || <math>\displaystyle s_3</math> || <math>\displaystyle s_2</math> || <math>\displaystyle s_1</math> || <math>\displaystyle s_0</math>
| |
| |-
| |
| |
| |
|
| |
| |}
| |
|
| |
| </center>
| |
|
| |
| <rightoption reply="Dobrze">jest automatem minimalnym</rightoption>
| |
|
| |
| <wrongoption reply="Źle">rozpoznaje język <math>\displaystyle \{w \in \{a,b\}^*:\ \sharp_aw = 2k,
| |
| \sharp_bw = 2l+1</math>, <math>\displaystyle k,l \geq 0\}</math></wrongoption>
| |
|
| |
| <wrongoption reply="Źle">rozpoznaje język <math>\displaystyle \{w \in \{a,b\}^*:\ \sharp_aw = 2k,
| |
| \sharp_bw = 2l</math>, <math>\displaystyle k,l \geq 0\}</math></wrongoption>
| |
|
| |
| <rightoption reply="Dobrze">rozpoznaje język <math>\displaystyle \{w \in \{a,b\}^*:\ \sharp_aw = 2k+1,
| |
| \sharp_bw = 2l</math>, <math>\displaystyle k,l \geq 0\}</math></rightoption>
| |
|
| |
| <wrongoption reply="Źle">rozpoznaje język <math>\displaystyle \{w \in \{a,b\}^*:\ \sharp_aw = 2k+1,
| |
| \sharp_bw = 2l+1</math>, <math>\displaystyle k,l \geq 0\}</math></wrongoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Które z poniższych równości dla wyrażeń regularnych są prawdziwe?
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle r^*r^*=r^*</math></rightoption>
| |
|
| |
| <wrongoption reply="Źle"><math>\displaystyle (r+s)^*=r^*+s^*</math></wrongoption>
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle (r^*+s^*)^*=(r^*s^*)^*</math></rightoption>
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle r+r=r</math></rightoption>
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle (rs)^*r=r(sr)^*</math></rightoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Wskaż języki regularne:
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle \{w \in \{a,b\}^*:\ \sharp_aw = \sharp_bw\ (mod\ 3)\}</math></rightoption>
| |
|
| |
| <wrongoption reply="Źle"><math>\displaystyle \{w \in \{a,b\}^*:\ \sharp_aw = \sharp_bw\}</math></wrongoption>
| |
|
| |
| <wrongoption reply="Źle"><math>\displaystyle \{w \in \{a,b\}^*:\ |w|=2^n, n > 0\}</math></wrongoption>
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle \{w \in \{a,b\}^*:\ \sharp_aw \cdot \sharp_bw = 100\}</math></rightoption>
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle \{a^n:\ n=3k </math> lub <math>\displaystyle n=5k,\ k \geq 0\}</math></rightoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Dany jest automat <math>\displaystyle \mathcal{A}=(S, A, s_0, f, F)</math>, gdzie
| |
| <math>\displaystyle S=\{s_0,s_1,s_2\}</math>, <math>\displaystyle A=\{a,b\}</math>, <math>\displaystyle F=\{s_0,s_1\}</math>,<br>
| |
|
| |
|
| |
| <center>
| |
| {| border=1
| |
| |+ <span style="font-variant:small-caps"></span>
| |
| |-
| |
| | <math>\displaystyle f</math> || <math>\displaystyle s_0</math> || <math>\displaystyle s_1</math> || <math>\displaystyle s_2</math>
| |
| |-
| |
| | <math>\displaystyle a</math> || <math>\displaystyle s_1</math> || <math>\displaystyle s_0</math> || <math>\displaystyle s_2</math>
| |
| |-
| |
| | <math>\displaystyle b</math> || <math>\displaystyle s_0</math> || <math>\displaystyle s_2</math> || <math>\displaystyle s_2</math>
| |
| |-
| |
| |
| |
|
| |
| |}
| |
|
| |
| </center>
| |
| Wskaż zdania prawdziwe:
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle L(\mathcal{A})=(a^2+b)^*(a+1)</math>.</rightoption>
| |
|
| |
| <wrongoption reply="Źle">Równoważny automat minimalny ma 2 stany.</wrongoption>
| |
|
| |
| <rightoption reply="Dobrze">Jeśli <math>\displaystyle w \in L(\mathcal{A})</math>, to dla każdych <math>\displaystyle v,u \in A^*</math> takich, że
| |
| <math>\displaystyle w=vbu</math> zachodzi <math>\displaystyle \sharp_av = 2k</math> dla pewnego <math>\displaystyle k \geq 0</math>.</rightoption>
| |
|
| |
| <wrongoption reply="Źle"><math>\displaystyle a^*b^* \subset L(\mathcal{A})</math>.</wrongoption>
| |
|
| |
| <wrongoption reply="Źle">Jeśli <math>\displaystyle w \in L(\mathcal{A})</math>, to <math>\displaystyle a^2b</math> jest podsłowem
| |
| słowa <math>\displaystyle w</math>.</wrongoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Dany niech będzie automat niedeterministyczny <math>\displaystyle \mathcal{A}_{ND}=(Q,
| |
| A, \{q_0\}, f, F)</math>, gdzie <math>\displaystyle Q=\{q_0, q_1, q_2\}</math>, <math>\displaystyle A=\{a,b\}</math>,
| |
| <math>\displaystyle F=\{q_2\}</math>,<br>
| |
|
| |
|
| |
| <center>
| |
| {| border=1
| |
| |+ <span style="font-variant:small-caps"></span>
| |
| |-
| |
| | <math>\displaystyle f</math> || <math>\displaystyle q_0</math> || <math>\displaystyle q_1</math> || <math>\displaystyle q_2</math>
| |
| |-
| |
| | <math>\displaystyle a</math> || <math>\displaystyle \{q_1\}</math> || <math>\displaystyle \{q_0,q_2\}</math> || <math>\displaystyle \{q_2\}</math>
| |
| |-
| |
| | <math>\displaystyle b</math> || <math>\displaystyle \emptyset</math> || <math>\displaystyle \emptyset</math> || <math>\displaystyle \{q_1\}</math>
| |
| |-
| |
| |
| |
|
| |
| |}
| |
| </center>
| |
|
| |
| Wskaż zdania prawdziwe:
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle L(\mathcal{A}_{ND})=a^2(a+ba)^*</math>.</rightoption>
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle L(\mathcal{A}_{ND})=a(aa^*b)^*aa^*</math>.</rightoption>
| |
|
| |
| <wrongoption reply="Źle">Równoważny automat deterministyczny posiada 3 stany.</wrongoption>
| |
|
| |
| <wrongoption reply="Źle"><math>\displaystyle L(\mathcal{A}_{ND})=a^2(a^*b)^*aa^*</math>.</wrongoption>
| |
|
| |
| <rightoption reply="Dobrze">Równoważny minimalny automat deterministyczny posiada 4 stany.</rightoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Twierdzenie orzekające o równości zachodzącej pomiędzy rodziną
| |
| języków regularnych a rodziną języków rozpoznawanych przez automaty
| |
| o skończonej liczbie stanów znane jest jako:
| |
|
| |
| <wrongoption reply="Źle">twierdzenie Nerode'a</wrongoption>
| |
|
| |
| <wrongoption reply="Źle">teza Churcha</wrongoption>
| |
|
| |
| <wrongoption reply="Źle">lemat Ardena</wrongoption>
| |
|
| |
| <wrongoption reply="Źle">lemat o pompowaniu</wrongoption>
| |
|
| |
| <rightoption reply="Dobrze">twierdzenie Kleene'ego</rightoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Wskaż monoid przejść automatu o następującej funkcji przejścia: <br>
| |
|
| |
| <center>
| |
| {| border=1
| |
| |+ <span style="font-variant:small-caps"></span>
| |
| |-
| |
| | <math>\displaystyle f</math> || <math>\displaystyle s_0</math> || <math>\displaystyle s_1</math> || <math>\displaystyle s_2</math> || <math>\displaystyle s_3</math>
| |
| |-
| |
| | <math>\displaystyle a</math> || <math>\displaystyle s_1</math> || <math>\displaystyle s_0</math> || <math>\displaystyle s_3</math> || <math>\displaystyle s_2</math>
| |
| |-
| |
| | <math>\displaystyle b</math> || <math>\displaystyle s_3</math> || <math>\displaystyle s_2</math> || <math>\displaystyle s_1</math> || <math>\displaystyle s_0</math>
| |
| |-
| |
| |
| |
| |}
| |
| </center>
| |
|
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle (\{\tau_{\mathcal{A}}(1),\tau_{\mathcal{A}}(a),\tau_{\mathcal{A}}(b),\tau_{\mathcal{A}}(ab)\},
| |
| \circ)</math></rightoption>
| |
|
| |
| <wrongoption reply="Źle"><math>\displaystyle (\{\tau_{\mathcal{A}}(1),\tau_{\mathcal{A}}(a)\},\circ)</math></wrongoption>
| |
|
| |
| <wrongoption reply="Źle"><math>\displaystyle (\{\tau_{\mathcal{A}}(1),\tau_{\mathcal{A}}(a),\tau_{\mathcal{A}}(ab)\},\circ)</math></wrongoption>
| |
|
| |
| <wrongoption reply="Źle"><math>\displaystyle (\{\tau_{\mathcal{A}}(1),\tau_{\mathcal{A}}(a),\tau_{\mathcal{A}}(b)\},\circ)</math></wrongoption>
| |
|
| |
| <wrongoption reply="Źle"><math>\displaystyle (\{\tau_{\mathcal{A}}(a),\tau_{\mathcal{A}}(b),\tau_{\mathcal{A}}(ab),\tau_{\mathcal{A}}(ba)\},
| |
| \circ)</math></wrongoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Niech <math>\displaystyle L_1,L_2</math> będą językami regularnymi. Wskaż problemy
| |
| rozstrzygalne.
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle w \in L_1</math></rightoption>
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle w \in L_1 \cap L_2</math></rightoption>
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle L_1 \cap L_2 = \emptyset</math></rightoption>
| |
|
| |
| <rightoption reply="Dobrze">nieskończoność <math>\displaystyle L_1</math></rightoption>
| |
|
| |
| <rightoption reply="Dobrze"><math>\displaystyle L_1 = \emptyset</math></rightoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Algorytm determinizacji automatu:
| |
|
| |
| <rightoption reply="Dobrze">jest deterministyczny</rightoption>
| |
|
| |
| <wrongoption reply="Źle">działa w czasie wielomianowym</wrongoption>
| |
|
| |
| <wrongoption reply="Źle">może się zapętlić</wrongoption>
| |
|
| |
| <rightoption reply="Dobrze">działa w czasie eksponencjalnym</rightoption>
| |
|
| |
| <wrongoption reply="Źle">kończy działanie błędem, jeśli na wejściu podany został
| |
| automat deterministyczny</wrongoption>
| |
|
| |
| </quiz>
| |
|
| |
|
| |
| <quiz>
| |
| Wskaż zdania prawdziwe:
| |
|
| |
| <rightoption reply="Dobrze">istnieje algorytm minimalizacji automatu działający w
| |
| czasie <math>\displaystyle n\log n</math></rightoption>
| |
|
| |
| <wrongoption reply="Źle">żaden algorytm minimalizacji nie może działać szybciej niż
| |
| w czasie <math>\displaystyle O(n^2)</math></wrongoption>
| |
|
| |
| <wrongoption reply="Źle">algorytm minimalizacji zawsze zwróci automat o mniejszej
| |
| liczbie stanów niż automat podany na wejściu</wrongoption>
| |
|
| |
| <wrongoption reply="Źle">algorytmy minimalizacji są algorytmami niedeterministycznymi</wrongoption>
| |
|
| |
| <wrongoption reply="Źle">algorytmy minimalizacji nie działają dla automatów jednostanowych</wrongoption>
| |
| </quiz>
| |
