- Stahuj zápisky z přednášek a ostatní studijní materiály
- Zapisuj si jen kvalitní vyučující (obsáhlá databáze referencí)
- Nastav si své předměty a buď stále v obraze
- Zapoj se svojí aktivitou do soutěže o ceny
- Založ si svůj profil, aby tě tví spolužáci mohli najít
- Najdi své přátele podle místa kde bydlíš nebo školy kterou studuješ
- Diskutuj ve skupinách o tématech, které tě zajímají
Studijní materiály
Zjednodušená ukázka:
Stáhnout celý tento materiálTEORIE FORMÁLNÍCH JAZYKŮ A GRAMATIKKonečné automatySestrojte deterministický konečný automat, který akceptuje jazyk L ( (a, b(*, obsahující slova x, které splňují současně podmínkydélka slova je dělitelná 3 slovo x začíná písmenem a a končí písmenem ba zamítne všechny ostatní slova.Určete jazyk, který rozpozná konečný automat
Navrhněte konečný automat, který rozpozná všechny slova nad abecedou A = (a,b(, které obsahují tři výskyty písmena a. Zapište tento znak regulárním výrazem. (tj. Pomocí operací zřetězení, sjednocení, *)Najděte jednosměrný deterministický konečný automat, který akceptuje všechna slova z (0,1(* takové, že každá 0 má bezprostředně vpravo od sebe symbol 1.Nechť M = ((q0, q1, q2(, (a, b(, (, q0, (q2() je nedeterministický konečný automat, kde((q0, a) = (q1, q2(,((q1, a) = (q0, q1(,((q2, a) = (q0, q2(((q0, b) = (q0(,((q1, b) = (((q2, b) = (q1( Najděte deterministický konečný automat, který rozpoznává T(M).Sestrojte konečný automat M tak, abyL(M) = (aa)*(bb)*L(M) = 1(1 ( 0)*1L(M) = (11 ( 01)* V případě (b) sestrojte deterministický i nedeterministický konečný automat.Nechť jsou dány konečné automaty M1 = (Q1, (1, (1, s1, F1) a M2 = (Q2, (2, (2, s2, F2)Navrhněte konečný automat proL(M1)R(zrcadlový obraz jazyka L(M1))L(M1) ( L(M2)Pref(L(M2)), tj. množinu všech prefixů jazyka L(M2)Sestrojte deterministický konečný automat, který pracuje s abecedou A = (a, b( a akceptuje ty slova, ve kterých se před každým výskytem písmene a vyskytuje slovo bbb.L = L(M) pro konečný automat M
Určete jazyk LR.Jaký jazyk rozpoznává konečný automat daný diagramem?
Akceptuje tento automat slovo 1000? Proč?Sestrojte k danému nedeterministickému konečnému automatu ekvivalentní deterministický konečný automat.
Sestrojte k danému nedeterministickému konečnému automatu ekvivalentní deterministický konečný automat.
Určete jazyky, které rozpoznávají konečné automaty:a) b)c)Napište tři slova, které automatzamítnepřijme
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}Napiš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}Určete konečný automat, který rozpoznává jazyk ab(c (a(cb.Sestrojte konečný automat, který přijme jazyk L= (a i b j c3( i,j ( 1(. Určete konečné automaty, které akceptují jazyky L1 = (aaa, aa, aaaa( a L2 = (aaa, aa, aaaa((.Je daný regulární jazyk L= 0(1(0)(1. Sestrojte deterministický konečný automat, který ho rozpoznává.Navrhněte konečný automat, který rozpozná všechny slova nad abecedou A = (a,b(, obsahující tři výskyty písmena a. Zapište tento jazyk regulárním výrazem (t.j. pomocí operací zřetězení, sjednocení, ().Ukažte, že jazyk L=(a2ibi( i ( 0 (není regulární (tj. nedá se rozpoznat konečným automatem).Určete maximální počet cyklů v redukovaném deterministickém konečném automatu rozpoznávajícím konečný jazyk. (Poznámka: redukovaný automat je automat s nejmenším počtem stavů, který rozpoznává daný jazyk. )Sestrojte konečné automaty M2 a M3 tak, aby M2akceptoval všechny přirozené čísla (zapásané v desítkové soustavě) dělitelné číslem 2, M3akceptoval všechny přirozené čísla (zapsané v desítkové soustavě) dělitelné číslem 3.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.Určete konečný deterministický automat, který akceptuje jazyk L = ab(aa. Turingův strojSestrojte Turingův stroj, který akceptuje slova BaiBajB v případě, že i( j. Popište (vysvětlete) činnost vámi navrhnutého Turingova stroje.Sestrojte Turingův stroj, který pro vstup BaiBajB dá výstup Ba(i-j(B. Vysvětlete činnost vámi navrhnutého Turingova stroje.Navrhněte Turingův stroj, který pro vstupy tvaru BamBanB realizuje výstup BamBanB pro m ( n a BanBamB pro m(nUrčete Turingův stroj, který pro vstup BxB realizuje výstup ve tvaru BxxRB.Sestrojte Turingův stroj, který pro vstupy tvaru 1iB1j dává výstup 1iB1jB1i+jSestrojte a) deterministický Turingův stroj, který prověří abecední pořadí slov x1, x2, x3 při vstupu Bx1Bx2Bx3 b) deterministický Turingův stroj, který uspořádá slova x1, x2 do abecedního pořadí (vstup: Bx1Bx2B)7. Sestrojte Turingův stroj, který přijme jazyk (an(a3n+1: n ( 1(.Sestrojte Turingův stroj, který akceptuje slova BaiBa3iB.Sestrojte Turingův stroj, který akceptuje slova BwBwB pro libovolné w nad abecedou m(a, b, c(.Daný je Turingův stroj
Zvolte neprázdné slovo, které tento TS akceptuje. Napište odvození pro zvolené slovo.Sestrojte Turingův stroj, který akceptuje slova BwaaawB pro libovolné w nad abecedou {a,b}.Sestrojte Turingův stroj, který rozpozná jazyk L = (ww: w ( ( a,b (( (.Sestrojte Turingov stroj, který sčítá dvě čísla zapsané unárně, t.j. stroj začne výpočet se vstupnou páskou (ai(aj( a ukončí výpočet v koncovém stave, když je na pásce slovo (ai(aj(ai(j(.Je daný Turingov stroj, ktorý príjme jazyk L. Navrhněte Turingov stroj, který příjme jazyk L1= LabL.Sestrojte Turingův stroj, který příjme jazyk (an(a3n+1 : n(1(.0L-systémyJaký jazyk určuje T0L-systém G =((, P, (( pro ( = (a, b, c(, ( = b, P = (P1, P2, P3(, P1 = (a(a, b(ba2, c(c( P2 = ( a(a2, b(b, c(c( P3 = (a((, b(ca2, c(c( Uveďte příklad odvození v tomto systému.Navrhněte a) T0L systém b) E0L systém který generuje jazyk L = (b2, a6, a8, a10(Daný je T0L-systém G = ((a,b(,(a(a2,b(b3(,(a(a3,b(b2(,ab( Určete L(G). Pro jaké hodnoty i platí, že aibi ( L(G)?Zásobníkový automatUrčete zásobníkový automat, který rozpoznává jazyk L = (a3ibiajbj+1: i, j ( 1(.Navrhněte zásobníkový automat, který přijme jazyk L = (waabwR(w ( (a, b(*(.Najděte zásobníkové automaty, které rozpoznávají koncovým stavem následující množiny:(w(w ( (0, 1(* a w se skládá ze stejného počtu symbolů 0 a 1(.(anbm(n ( m ( 2n(Množinu generovanou gramatikou
G = ((S, A(, (a, b(, (S(aAA, A(bS, A(aS, A(a(, S)
Množinu správně vytvořených aritmetických výrazů v jazyce Fortran.Předpokládejte, že identifikátory proměnných mohou mít libovolnou délku větší nebo rovnající se 1.Nechť L = N(M) pro nějaký zásobníkový automat. Ukažte, že L = N(M1) pro nějaký zásobníkový automat M1, který má pouze jeden stav.Sestrojte zásobníkový automat, který rozpozná jazykL = (w ( (a, b(*: (w(a = 2(w(b(.Sestrojte zásobníkový automat rozpoznávající jazykL = (abwwR(w ( (a, b(*(.V zásobníkovém automatu platí/neplatí (q, xy, (() |--* (q´, y, (() implikuje (q, x, () |--* (q´,(, (). Svoje tvrzení zdůvodněte.Sestrojte zásobníkový automat rozpoznávající jazyk, který se rovná jazyku generovanému gramatikouS(aAAA(bS(aS(aUrčete část přechodové funkce zásobníkového automatu, která umožňuje převést následující krok odvození (q,aa,bc) |-- (q1,a,c)10. V zásobníkovém automatu A platí ( q, aaab, bbc) |-- *( p, b, c ) Určete odpovídající část přechodové funkce.Určete zásobníkový automat, který přijme jazyk L = {ai (bc)2i(i (1 } Ke každé bezkontextové gramatice G existuje zásobníkový automat M takový, že L(G)=L(M). DokažteSestrojte zásobníkový automat, který rozpozná jazyk L=(1i21i ( i(0(.Napište bezkontextovou gramatiku generující jazyk L=(ai bj a cj di ( i,j ((( .K dané bezkontextové gramatice vytvořte ekvivalentní gramatiku bez pravidel typu A ( B, A,B ( N. P:A ( aA ( BB ( bB ( CC ( cC ( c Je daný jazyk L gramatikou s pravidlyA ( AAaA ( ba) Zadejte zásobníkový automat, který rozpoznává jazyk L i) koncovými stavy,ii) prázdným zásobníkem.b) Rozhodněte, který vztah je mezi jazyky L a R, kdeR = ( w ( w((a,b(( #a(w)+1 = #b(w) (. Zdůvodněte.(Symbol #a(w) označuje počet výskytů písmena a v slově w).Navrhněte zásobníkový automat, který příjme jazyk L =(w wR (w ( (a,b(( ( ( (a3b(.Sestrojte zásobníkový automat, který rozpozná jazyk L=(1i21i ( i(0(.Vytvořte zásobníkový automat, který rozpozná jazyk L= (aibjci : i,j ( 1(Je daný jazyk L gramatikou s pravidlyA ( AAaA ( ba) Zadejte zásobníkový automat, který rozpoznává jazyk L i) koncovými stavy,ii) prázdným zásobníkem.b) Rozhodněte, jaký vztah je mezi jazyky L a R, kdeR = ( w ( w((a,b(( #a(w)+1 = #b(w) (. Zdůvodněte.Navrhněte zásobníkový automat, který příjme jazyk L =(w wR (w ( (a,b(( ( ( (a3b(.Určete zásobníkový automat, který akceptuje jazyk L = (wawR: w( (a,b(((.Určete zásobníkový automat, který akceptuje jazyk L = (wawRwawR: w( (a,b(((.V zásobníkovém automate platí (q,aaa,XXZ) (( (p,aa,XZ). Určete ((q,a,X).Navrhněte zásobníkový automat, který příjme jazyk L =(waabwR (w ( (a,b(( (.Sestrojte zásobníkový automat, který přijímá jazyk L. L = {0n1n(n ( 0}.Mějme zásobníkový automat P: P = ({q, p}, {a, b}, {a, b, S, Z},(, q, Z, {p}), kde zobrazení je definováno takto: ((q, a, () = {(q, a)} ((q, b, () = {(q, b)} ((q, (, () = {(q, S)} ((q, (, aSa) = {(q, S)} ((q, (, bSb) = {(q, S)} ((q, (, SZ) = {(p, ()}.Ukažte jaký jazyk přijme tento automat.Mějme bezkontextovou gramatiku G = ({R, K I}, {a, (, +, *, (, )}, P, R)s pravidly R(R+K(K K(KI(I I(I*((R)(a((.Sestrojte zásobníkový automat, který přijme jazyk L(G).Mějme zásobníkový automat P,kde P = ({q0, q1}, {0, 1}, {X, Z0}, (, q0, Z0, ()kde zobrazení ( je dané takto: ((q0, 0, Z0) = {(q0, XZ0)}((q1, 1, X) = {(q1, ()} ((q0, 0, X) = {(q0, XX)}((q1, (, X) = {(q1, ()} ((q0, 1, X) = {(q1, ()}((q1, (, Z0) = {(q1, ()}.Vytvořte gramatiku G = (N, T, P, S) takovou, že L(P) = L(G).Vytvořte zásobníkový automat, který přijímá jazykL = (anbm( n ( m( 2n(.Pro gramatikya) S(aSb(( b) S(AS(b A(SA(a c) S(SS(A A(0A1(S(01vytvořte zásobníkové automaty modelující syntaktickou analýzu shora dolů a zdola nahoru. Je daná bezkontextová gramatikaG = ((S, A, B(, (a, b, c, d(, P, S),kde P obsahuje pravidla: S(Aa A(bB(Ac B(d.Vytvořte pro tuto gramatiku zásobníkový automat.Uvažujme zásobníkový automat A = ({q1, q2}, {0, 1}, {Z, A}, (, q1, Z0, ()kde ( je definováno takto: ((q1, 0, Z) = {( q1, AZ)} ((q1, 0, A) = {( q1, AA)} ((q1, 1, A) = {( q2, ()} ((q2, 1, A) = {( q2, ()} ((q2, (, Z) = {( q2, ()}.Jaký jazyk generuje tento automat?Uvažujme zásobníkový automat A = ({p, q}, {a, b}, {a, b, S, Z}, (, q, Z, {p}()kde ( je definováno takto: ((q, a, () = {(q, a)} ((q, b, () = {(q, b)} ((q, (, () = {(q, S)} ((q, (, aSa) = {(q, S)} ((q, (, bSb) = {(q, S)} ((q, (, ZS) = {(q, ()}.Jaký jazyk generuje tento automat?Buď G = ({E, T, F}, {a, *, +, (, )}, P, E)bezkontextová gramatika, kde P obsahuje pravidla: E(E+T E(T T(T*F T(F F((E) F(a.Definujte zásobníkový automat pro tuto gramatiku.Sestrojte zásobníkový automat, akceptující doplněk následujících jazyků:a) {anbncn; n ( 1} b) {ww; w ( {a, b}*} c) {ambnambn; m, n ( 1}.Nalezněte deterministický zásobníkový automat akceptující jazyk:{0i1j; j ( i}.Sestrojte deterministický zásobníkový automat akceptující jazyk: (a2icbi: i ( 0(.Sestrojte deterministický zásobníkový automat akceptující jazyk (a2i+1bi: i ( 0(.Sestrojte deterministický zásobníkový automat akceptující jazyk (x: x ( (a, b(* a (x(a = (x(b(.Sestrojte deterministický zásobníkový automat akceptující jazyk (xcxR: x ( (a, b(*(.Je dán deterministický zásobníkový automat M a) Napište 4 slova přijímaná automatem M a jejich odvození.b) Napište 4 slova zamítnutá automatem M a jejich odvození.c) Jaký jazyk akceptuje tento automat M?Sestrojte deterministický zásobníkový automat akceptující jazyk: (aibjc: i ( j ( 0(.GRAMATIKY A JAZYKYUrčete jazyk, který generuje gramatika S(aAb2S(bBA(a2BbB(aBb4B((Dané jsou gramatikyG1: S(SaS(bG2: S(aS(bG3: S(aSaS(bG4: S(SS(aG5: SCaSS(b Vyjmenujte, které z nich jsoua) regulárnív CHNT v GNTv 2-standartním tvaruv operátorovém tvaruV gramatice G = (N, T, P, S) s pravidlyS(ABCA(aAA(aB(bBdB(CC(c odvoďte všechny slova z L(G) délky 6.Nechť G je gramatika s pravidlyS(SSS(aaSBS(bSaaS(( Rozhodněte, zda L(G) = (x: x((a, b(*, (x(a=2(x(b( Zdůvodněte svoje tvrzení.Sestrojte gramatiku pro jazyk N(M), kdeM = ((q0, q1(, (0, 1(, (Z0, X(, (, q0, Z0, () a ( je dané takto: ((q0, 1, Z0) = ((q0, XZ0)(,((q0, (, Z0) = ((q0, ()(((q0, 1, X) = ((q0, XX)(,((q1, 1, X) = ((q1, ()(((q0, 0, X) = ((q1, X)(,((q1, 0, Z0) = ((q0, Z0)(Zvolte tři slova x, y, z. Určete:délky těchto slovpočet výskytů jednotlivých písmen ve slovechvšechny prefixy xvšechny sufixy yvšechny podslova zxy3z, y6z0, xRy(zR)R, kde zR je zrcadlový obraz z.Rozhodněte, zda pro jazyky L1, L2, L3 platí:L1(L2 ( L3) = L1L2 ( L1L3L1(L2 ( L3) = L1L2 ( L1L3Rozhodněte, jestli následující dvojice regulárních výrazů generují stejný jazyk.E1 = ( ( aa*E2 = a*E1 = A*B*E2 = (A ( B)*pro které E1, E2 jsou výrazy E1E2* ( ( a E1E2* ekvivalentní?Napište gramatiku, která určuje jazyk:{aibicj: i, j ( 0}{aibj: i = 2j anebo j = 2i}{ai+3b2i+1: i (.0}{aibjcjdie3: i, j ( 0}Napište gramatiku, která generuje jazykL = (w ( (a, b(*: (w(a = 2(w(b(.Zjistěte, jestli jsou následující gramatiky jednoznačné:G1:S(aAcG2:S(aSS(bSS(SaA(aAS(bSbA(AaA(aAbA(cA(acbDokažte, že průnik regulárního a bezkontextového jazyka je bezkontextový jazyk.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}Nechť pro jazyk L1 platí, že L1 ( (a, b, c(*((L1) = ((n, j, 2n): n, j ( 1(Uveďte příklad regulárního jazyka L1 s touto vlastností.Uveďte příklad bezkontextového (neregulárního) jazyka s touto vlastností.Uveďte příklad bezkontextového jazyka, který nemůžeme rozpoznat deterministickým zásobníkovým automatem.Daná je gramatika G:S(aS(S1S1(bS1(S2S2(cS2(c Najděte ekvivalentní gramatiku bez pravidel typu A(B.Převeďte danou gramatikuA(Ab(a na ekvivalentní gramatikuv Greibachovém normálním tvarutypu (1, 1, 0)typu (0, 2, 1)V gramatice s pravidly S(ABCA(aAA(aB(bBdB(CC(c odvoďte všechny slova z L(G) délky 8. Nakreslete příslušné stromy odvození.Ukažte, že gramatika s přepisovacím pravidlem A(AA je víceznačná. Najděte ekvivalentní pravidla, které tuto vlastnost odstraní.Daná je gramatika G = ((A, B, C, D, E(, (+, *, (, ), a(, P, A)P: A(CB B(+CB(e C(ED D(*ED(e E((A)(aZjistěte, zda jazyk L(G) je prázdnýZjistěte, zda G obsahuje nedostupné nebo nadbytečné symboly.Transformujte G na ekvivalentní gramatiku bez ( pravidel.Transformujte G na Chomského normální tvar.Vytvořte derivační strom, levé a pravé odvození pro řetězec (a+a)*a.Daná je gramatika G = ((A, A, B(, (a, b(, P, S), která má pra
Vloženo: 24.04.2009
Velikost: 1,18 MB
Komentáře
Tento materiál neobsahuje žádné komentáře.
Mohlo by tě zajímat:
Skupina předmětu IB002 - Návrh algoritmů I
Reference vyučujících předmětu IB002 - Návrh algoritmů I
Podobné materiály
- IA039 - Architektura superpočítačů a intenzivní výpočty - Skripta
- IB002 - Návrh algoritmů I - Skripta
- IB102 - Automaty a gramatiky - Skripta ostrava
- MA007 - Matematická logika - Skripta_18_stran
- MB000 - Matematická analýza I - Skripta_upol
- MB005 - Základy matematiky - Skripta dokonceny_niederle
- MB005 - Základy matematiky - Skripta_niederle_2002
- MB005 - Základy matematiky - Skripta_Rosicky
- MB101 - Matematika I - Skripta dvoji_pohl_svazy
- MB101 - Matematika I - Skripta ekviv
- MB101 - Matematika I - Skripta gener
- MB101 - Matematika I - Skripta grupy_polog
- MB101 - Matematika I - Skripta homomor_grup
- MB101 - Matematika I - Skripta kombin_variace
- MB101 - Matematika I - Skripta mnoziny
- MB101 - Matematika I - Skripta permut
- MB101 - Matematika I - Skripta princip_exkluze_inkluze
- MB101 - Matematika I - Skripta relace
- MB101 - Matematika I - Skripta svazy
- MB101 - Matematika I - Skripta usporadane_mny
- MB101 - Matematika I - Skripta uziti_exkluze_inkluze
- MB101 - Matematika I - Skripta zbytky
- MB101 - Matematika I - Skripta zobrazeni
- MB101 - Matematika I - Skripta Čisla_vlastnosti
- MB102 - Matematika II - Skripta koreny_polynom
- MB102 - Matematika II - Skripta okruhy_polynom
- MB102 - Matematika II - Skripta okruhy_telesa
- MB102 - Matematika II - Skripta rac_lom_fce
- MB102 - Matematika II - Skripta vlast_polynomu_delitel
- MB104 - Matematika IV - Skripta z.dosla
- PA008 - Překladače - Skripta a
- PA102 - Technologie informačních systémů I - TIS_I_skripta
- PB006 - Principy programovacích jazyků - Skriptaprincipy_programovacich_jazyku_zkusto
- PB006 - Principy programovacích jazyků - Skripta_2002
- PB007 - Analýza a návrh systémů - Skripta
- PB007 - Analýza a návrh systémů - Skripta_163_stran
- PB114 - Datové modelování I - Skripta
- PB151 - Výpočetní systémy - Skripta
- PB154 - Základy databázových systémů - Skripta complete_cz
- PB156 - Počítačové sítě - Skripta 1
- PB156 - Počítačové sítě - Skripta 2
- PV017 - Bezpečnost informačních technologií - Skripta
- PV077 - UNIX -- programování a správa systému II - Skripta
- PV058 - Informační systémy ve státní správě I - Skripta ISstatnisprava
- PV058 - Informační systémy ve státní správě I - Skripta ISstatnisprava1
Copyright 2023 unium.cz. Abychom mohli web rozvíjet a dále vylepšovat podle preferencí uživatelů, shromažďujeme statistiky o návštěvnosti, a to pomocí Google Analytics a Netmonitor. Tyto systémy pro unium.cz zaznamenávají, které stránky uživatel na webové stránce navštívil, odkud se na stránku dostal, kam z ní odešel, jaké používá zařízení, operační systém či prohlížeč, či jaký má preferenční jazyk. Statistiky jsou anonymní, takže unium.cz nezná identitu návštěvníka a spravuje cookies tak, že neumožňuje identifikovat konkrétní osoby. Používáním webu vyjadřujete souhlas použitím cookies a následujících služeb: