Skripta Teorie_Jaz_Aut

bo nesplňují pumpovací větu.
Kontrolní otázky z Teorie formálních jazyků a automatůDefinujte jazyk.Definujte slovo.Definujte operaci iterace jazyka. Definujte operaci zřetězení jazyka. Určete L* pro L = ab*c . Uveďte všechna slova délky 6 patřící do L*.Pro L = ab*(c ( a) určete nejkratší slova z L2. Napište slovo z jazyka L= (aba)*ac*.Pro L = ab* určete nejkratší slovo z L2.Uveďte příklad slova délky 5 patřící do jazyka L = ab*(ca)*.Rozhodněte, zda prázdné slovo patří do jazyka L = b*(ca)*.Definujte přechodovou funkci konečného automatu.Definujte přechodovou funkci nedeterministického konečného automatu.Definujte přechodovou funkci zásobníkového automatu.Definujte přechodovou funkci Turingova stroje.Charakterizujte přechodovou funkci deterministického a nedeterministického konečného automatu.Definujte konfiguraci konečného automatu.Definujte konfiguraci zásobníkového automatu.Definujte konfiguraci Turingova stroje.Definujte krok odvození konečného automatu.Definujte krok odvození zásobníkového automatu.Definujte krok odvození Turingova stroje.Definujte jazyk přijatý zásobníkovým automatem s koncovými stavy.Definujte jazyk přijatý zásobníkovým automatem s prázdným zásobníkem.Definujte jazyk přijatý Turingovým strojem.Definujte jazyk generovaný bezkontextovou gramatikou. Definujte regulární gramatiku.Definujte bezkontextovou gramatiku.Definujte kontextovou gramatiku.Definujte gramatiku typu 0.Kdy je gramatika redukovaná? Definujte krok odvození v regulární gramatice.Definujte krok odvození v bezkontextové gramatice.Definujte krok odvození v kontextové gramatice.Definujte krok odvození v gramatice typu 0.Charakterizujte gramatiku v Greibachové normálním tvaru.Charakterizujte gramatiku v Chomského normálním tvaru. Uveďte příklady.Napište gramatiku v Chomského normálním tvaru, která generuje jazyk L= (bac(.Napište gramatiku v Chomského normálním tvaru, která generuje jazyk L= a(b.Charakterizujte redukovanou gramatiku.Uveďte příklad regulárního jazyka.K jazyku z předešlého bodu napište gramatiku, která ho generuje.Uveďte příklad konečného jazyka.Uveďte tři příklady regulárních jazyků.Uveďte tři příklady bezkontextových jazyků.K jazyku z bodu 28 napište gramatiku, která ho generuje.Uveďte příklad bezkontextového jazyka, který není regulární.Uveďte příklad kontextového jazyka nad jednoprvkovou abecedou.Uveďte příklad kontextového jazyka, který není bezkontextový.Kdy je konečný automat deterministický?Jazyky rozpoznávané zásobníkovými automaty jsou totožné s jazyky generovanými ............gramatikami.Jazyky rozpoznávané lineárně ohraničenými automaty jsou totožné s jazyky generovanými ............gramatikami.Jazyky rozpoznávané Turingovými stroji jsou totožné s jazyky generovanými ............gramatikami.Jazyky rozpoznávané ............. automaty jsou totožné s jazyky generovanými regulárními gramatikami.Jazyky rozpoznávané ............. automaty jsou totožné s jazyky generovanými bezkontextovými gramatikami.Jazyky rozpoznávané ............. automaty jsou totožné s jazyky generovanými gramatikami v Chomského normálním tvaru.Jazyky rozpoznávané ............. automaty jsou totožné s jazyky generovanými kontextovými gramatikami.Jazyky rozpoznávané ............. automaty jsou totožné s jazyky generovanými gramatikami typu 0.Jazyky rozpoznávané konečnými automaty jsou totožné s jazyky generovanými ................gramatikami.Vysvětlete jakou roly má zásobník v zásobníkovém automatu.V zásobníkovém automatu A platí ( q, aaab, bbc) |-- *( p, b, c ).Určete odpovídající část přechodové funkce.Definujte jazyk přijatý konečným automatem.Definujte jazyk přijatý zásobníkovým automatem s prázdným zásobníkemJazyk L= { a3i+1 b4 c2i: i> 1 } je /není bezkontextový je /není regulárníDefinujte operaci zřetězení jazyka .Určete L.L pro L = ab*(ca)*.Uveďte všechna slova délky 5 patřící do L.L .Jazyk L= { ai | i > 0 } je regulární, bezkontextový, kontextový, typu 0. (Nehodící se škrtněte.) Charakterizujte redukovanou gramatiku .Určete strom odvození slova ((( )a)( b))v gramatice S ----> (S) | SS | a | b | . Odvození AaBB ==> AbBje možné v gramatice regulární, bezkontextové, kontextové , typu 0.(Nehodící se škrtněte.)V zásobníkovém automatu A platí ( q, aaab, bbc) |-- * ( p, b, a) .Určete odpovídající přechodovou funkci Pro kontextovou gramatiku s pravidlyAA ---> AaAB ---> cBB ---> bBproveďte jeden krok odvození AABB ==>Určete pravidla regulární gramatiky pro odvozeníaB ==>* aabcCUrčete strom odvození (derivační strom) slova { }{{ }}[ ] v gramatice s pravidlyS ---> {S} | | [ S] | SS |Pro L = ab*(c ( a) uveďte všechna slova délky 5 patřící do L.L .Napište gramatiku v Chomského normálním tvaru, která generuje jazyk L= a(b .Odvození abXZZ ( abcZZZ je možné / není možné v gramatice v Greibachové normálním tvaru?Uveďte příklad konečného automatu.Uveďte příklad slova, generovaného gramatikou G,S ( aSSa (bNakreslete strom odvození slova z bodu 77.Kolik různých odvození slova z bodu 77 v gramatice G existuje?Uveďte příklad takého odvození.Napište gramatiku v Chomského normálním tvaru, která generuje jazyk L= ba( .Uveďte příklad zásobníkového automatu.Napište příklad počáteční konfigurace automatu z předešlého bodu.Uveďte příklad slova, které automat z bodu 82 přijme.Uveďte příklad odvození terminálního slova v gramatice S ----> aSS | Sb | cNapište příklad koncové konfigurace pro konečný automat A=(K, (, ( , qo,F) , kde K={ q0,q1 }, ( = {a}, ((q0 ,a) = q1 , ( (q1 ,a) = q1 , F = { q1}Využití Turingových strojůCharakterizujte rozdíl mezi deterministickým a nedeterministickým automatem?Uveďte příklad kontextového jazyka nad jednoprvkovou abecedouCharakterizujte neformálně konfiguraci automatu. Za jakým účelem byla zavedenáCo je charakteristické pro normální tvary gramatik a k čemu slouží ? Napište libovolnou konkrétní regulární gramatiku G.Napište příklad slova w, který není v L(G).Jazyk (ai bj ( i, j ( 1 ( je regulární / bezkontextový?Jazyk, který obsahuje právě jedno slovo je - není regulární.Napište pravidla, které umožňují v gramatice odvození XZ (( aXZaabB.V zásobníkovém automatu bylo při odvození (q,aaa,XXZ) ((( (q,a, Z) použito vícekrát ((q,a,X)( x. Určete x.Načrtněte konečný automat, který rozeznává jazyk L= (aba(.Odvození abXZZ ( abZZZ je možné / není možné v gramatice v Greibachové normálním tvaru?Jaké pravidlo bylo použito při odvození v bodě 8Uveďte příklad slov u,v pro které platí uv = vu. Uveďte příklad slova, generovaného gramatikou G,S ( aSSa (b.Uveďte příklad odvození slova abba v gramatice z předešlého bodu.Uveďte 2 různá odvození slova z bodu 15 v gramatice G?Nechť v zásobníkovém automatu platí ((q,a,Y) = (p, a).Určete ( ve vztahu (q, aax, YZ) (p,ax, ()Uveďte příklad jazyka pro který platí L.L = LNapište příklad koncové konfigurace automatu se stavy Q = (a,b,c( F=(c(.Napište příklad počáteční konfigurace pro konečný automat A=(K, , , qo,F) ,kde K={ q0,q1 }, = {a}, ( q0 ,a) = q1 , (q1 ,a) = q1 , F = { q1}Určete pravidla umožňují v regulární gramatice odvozeníaB ==>* aabcCUrčete část přechodové funkce zásobníkového automatu, která umožňuje převést následující krok odvozeni (q,aa,bc) |-- (q1,a,c)Konfigurace automatu. Co to je. Za jakým účelem byla zavedená.Vyslovte Pumpovací lemu pro regulární gramatiky. Dokažte, že jazyk {aibi: i > 0 } není regulární.Dokažte, že jazyk L= aibi: i 0 není regulární. Zjistěte, zda jsou následující jazyky bezkontextové. Zdůvodněte.L = { a3nbn | n 1} Ln={a3nbn } n 1 Popište Postův korespondenční problém a uveďte příklad.Dickův jazyk. Jeho úloha při reprezentaci bezkontextových jazyků (t.j. Chomsky-Sch(tzenbergerova věta, znění). Ilustrujte platnost vety na dvou libovolně zvolených příkladech jazykůPopište postupy které by jste použili na zjištění, zda je daný jazyk bezkontextový. (Které tvrzení můžete použit když je daný jazyk bezkontextový? Které tvrzení můžete použít, když daný jazyk není bezkontextový?)Co víte o uzavřenosti tříd jazyků na zrcadlový obraz?Jazyky rozpoznávané ZA s koncovými stavy jsou totožné s jazyky rozpoznávanými ZA s prázdným zásobníkem. Dokažte.Napište libovolnou konkrétní bezkontextovou gramatiku G s 3 neterminály. Napište příklad slova w z L(G).Odvoďte slovo w v gramatice G.Kdy je automat deterministický?Napište pravidlo, které bylo použito při odvození aAbB ( aabB.V zásobníkovém automatu platí (q,aaa,XXZ) (( (p,aa,YXXZ). Určete ((q,a,X)Vyslovte a vysvětlete Pumpovací větu pro regulární jazyky.Ke každé bezkontextové gramatice G existuje zásobníkový automat M takový, že L(G)=L(M). Dokažte.Sestrojte gramatiku v GNT pro jazyk L =(wwR: w ( ( a,b (( (.Dokažte, že průnik dvou regulárních jazyků je regulární jazyk. Platí obdobná věta i pro bezkontextové jazyky?Parikhova věta a její použiti.Co víte o uzavřenosti tříd jazyků na průnik?Dané jsou jazyky L1=(a2ibj( i,j(0( a L2 =(ai(bb)i+1( i(0(.a) Napište příklady 2 slov patřících do L1.b) Napište příklady 2 slov patřících do L2.c) Určete L1 ( L2.d) Vypište nejkratší slova jazyka L1 (L2.V zásobníkovém automate platí (q,aaa,XXZ) (( (p,aa,XZ). Určete ((q,a,X). Rozhodněte zda platí 1(11)(1 =1((11)(.Navrhněte konečný automat, který příjme slova jazyka L=1(11)(11.Prověřte podle definice, že Vámi navrhnutý automat a) nepřijme slovo 1111. b) přijme slovo 111.Je daný jazyk L = b(bab)(a. a) Definujte homomorfizmus h tak, aby platilo h(L) = c( .b) Definujte homomorfizmus g tak, aby platilo že délka každého slova v g(L) je násobkem 3.c) Definujte substituci s tak, aby s(L)= d(.Nadefinujte abstraktný automat s následujícími dvěma páskami- se vstupní páskou, z které automat čte vstupní slovo, tak, že po přečtení symbolu ze vstupní pásky může čtecí hlava zůstat stát na aktuálním políčku anebo se může posunout doprava,- a s jednou zásobníkovou páskou.Platí následující tvrzení? Svoji odpověď zdůvodněte.Když je L je regulární jazyk, potom je i jazyk L2 - L regulární jazyk.Nakreslete stavový diagram některého konečného automatu s třemi stavy a jedním vstupním signálem.Napište příklad počáteční konfigurace automatuNapište příklad koncové konfigurace automatuJaký jazyk akceptuje automatUveďte příklad slova, který automat zamítneL=( ai bici ( i(((((aibj( i ( j ( 0 (Uveďte všechna slova délky tři, které patří do L.Zapište pomocí operací ., ( jazyk L nad abecedou (a,b(, který sestává ze slov začínajících písmenem a a končících písmenem b.Rozhodněte, zda platí 1(11=111(L1= a(b(, L2= b(a(. Uveďte dva příklady slov w ( a(b( ( b(a(.Rozhodněte, zda platí L(A1)= L(A2) pro V zásobníkovém automatu platí (q,aaa,XXZ) (( ( (p, a,YXXZ). Kolik kroků odvození minimálně bylo uskutečněno?Jazyk, který obsahuje právě jedno slovo je - není regulární.Napište pravidla, které umožňují v gramatice odvození XZ (( aXZaabB.Platí následující tvrzení?Když L1 je regulární jazyk, potom aj L1 L1 je regulární jazyk.Zdůvodněte.Načrtněte konečný automat, který rozeznává jazyk L= (aba(.Každý konečný jazyk je regulární. Dokažte.Nakreslete stavový diagram nějakého konečného automatu s 3 stavy a jedním vstupním signálem.b) Napište příklad počáteční konfigurace automatuc) Napište příklad koncové konfigurace automatud) Jaký jazyk akceptuje automatUveďte příklad slova, který automat zamítneL={ai bici ( i(((((aibj( i ( j ( 0 (Uveďte všechny slova délky tři které patří do L.Zapište pomocí operací ., ( jazyk L nad abecedou (a,b(, který sestává ze slov začínajících písmenem a a končících písmenem b.Rozhodněte zda platí 1(11=111(L1= a(b(, L2= b(a(. Uveďte příklad slova w ( a(b( ( b(a(.Rozhodněte, zda platí L(A1)= L(A2) pro Uveďte příklad jazyka pro který platí L+ = L(.Prázdné slovo patří do jazyka L1L2 právě tehdy když - patří do každého z jazyků L1, L2 - patří do jednoho z jazyků L1, L2L={ai bici ( i(((((aibj( i ( j ( 0 (Uveďte všechny slova délky tři které patří do L.Napište regulární gramatiku G vytvářející jazyk L= a(ba(.Odvoďte slovo ab v gramatice G.Napište pravidlo, které bylo použito při odvození aAB ( aabB.Odvození S ((aBaa ( abaa je možné / není možné uskutečnit v regulární gramatice.Napište jazyk daný gramatikou S((AA, A((a (b.Napište gramatiku, která generuje jazyk a(b(. Napište jazyk daný gramatikou S((AA, A((a ((Pumpovací věta je a) implikace b) ekvivalence.(Nesprávné škrtněte).Rozhodněte, či trojice (q0,(,w) určuje počáteční konfigurace Turingova stroje.Napište příklad takej konfigurace konečného automatu, která je současně počáteční i koncovou konfigurací.Napište příklad jazyka, který víte generovat gramatikou s dvěma neterminály a nedá se generovat gramatikou s jedním neterminálem.Zvolte libovolnou gramatiku v Chomského normálním tvare.Odvoďte jedno slovo v gramatice.Napište gramatiku, která generuje jazyk L={a6,a9}V zásobníkovém automate, v kterém platí (q, aab, AAB) (( (q, ab, AAB) určete ((q,a,A).S ( AAAAA ( A( aUrčte L(G).Gramatika z předešlého bodu je ........................:Jazyk z tohoto bodu je /není je regulární?{a,b(((aibj( i ( j ( 0 (. Určete L({aibj( i ( j } ( (aibj( j ( i} =Napište gramatiku, která generuje jazyk L={a3,a5}a(Definujte krok odvození Turingova stroje při pohybe hlavice doleva.V zásobníkovém automate, v kterém platí (q, aab, AAB) ( (q, ab, ABAB) určete ((q,a,A).L=(aibj( i ( j ( 0 ((b5. Platí / neplatí tvrzení a3b7(patří do jazyka L(Čím se liší kontextová gramatika od gramatiky typu 0?Rozhodněte, či trojice (q0,(,Z0) určuje počáteční konfiguraci zásobníkového automatu.Jazyk (an ( n ( 4(( je/ není bezkontextový.Nechť L má právě 2 slova. Potom L2 a) právě 4 slovab) nejvíc 4 slovaUrčete která možnost je správná.Rozhodněte zda platí a(a = aa(Jazyk (a (log n( ( n ( 4(( je/ nie je bezkontextový. (k( označuje celou část čísla k.Napište příklad jazyka pro který platí L = L(Napište nejkratší slovo jazyka ab(a(bc)(Jazyk L = (bba5n ( n ( 4 ( je/ není bezkontextový. (abab)( ( ab( =Rozhodněte, či platí abb(c = ab(cV Konečném automate platí (q, aw)(( (p,w). Určete ((q,a) = Dané jsou pravidla A ( aab, B ( aaA. Odvoďte z B terminální slovo. Jaký jazyk generuje konečný automat se symboly a,b,c, kterého všechny stavy jsou koncové?Napište gramatiku, která generuje jazyk L={a3, a6, a9 }.