- 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álvidlaS(ba(aBA(a(aS(bAAB(b(bS(aBB Ukažte, že tato gramatika je víceznačná (vezměte např. slovo aabbab). Pokuste se najít ekvivalentní jednoznačnou gramatiku.Gramatiku s pravidlyS(A(BA(aB(bS(bB(AB(bAC(AS(b Transformujte na ekvivalentní gramatiku bez nadbytečných symbolů.Ke gramatice S(A(BA(C(DB(D(EC(S(a(eD(S(bE(S(c(e najděte ekvivalentní vlastní gramatiku.Vytvořte algoritmus, kterým je možné zjistit, zda gramatika G je nebo není gramatikou bez cyklu.V gramaticeS(ABA(BS(bB(SA(a odstraňte levou rekurzi. Odvození AaBB(AbB je možné v gramatice regulární, bezkontextové, kontextové, typu 0. (Nehodící se škrtněte) Určete strom odvození slova ((( )a)( b)) v gramatice S((S) | SS | a | b |Jazyk L= { ai | i > 0 }je regulární, bezkontextový, kontextový, typu 0.(Nehodící se škrtněte.)Definujte operaci zřetězení jazyka . Určete L.L pro L = ab*(c a). Uveďte všechna slova délky 5 patřící do L.L .Definujte operaci iterace jazyka . Určete L* pro L = ab*c . Uveďte všechna slova délky 6 patřící do L* .Určete strom odvození (derivační strom) slova { }{{ }}[ ] v gramatice s pravidly S({S} | | [ S] | SS | Jazyk L= { a3i+1 b4 c2i: i> 1 }je / není bezkontextový je / není regulárníNapište slovo z jazyka L= (aba)*ac*Uveďte příklad odvození terminálního slova v gramatice S(aSS | Sb | cRozhodněte o jazycích L1, L2 a L3, zda jsou bezkontextové. Svoje tvrzení zdůvodněte.L1 = (ai bi cj dj ( i,j (((L2 = (ai bj ci dj ( i,j (((L3 = (ai bj cj di ( i,j (((Je daný jazyk L gramatikou s pravidlyA ( AAaA ( ba) Určete ekvivalentní gramatiku v GNT.b) Zadejte zásobníkový automat, který rozpoznává jazyk L.c) Rozhodněte, jaký vztah je mezi jazyky L a R, kdeR = ( w ( w((a,b(( #a(w)+1 = #b(w) (. Zdůvodněte.d) Napište gramatiku, která generuje jazyk L(.Pro gramatiku s pravidlyAA(AaAB(cBB(bBproveďte jeden krok odvození AABB(.Napište množinu všech řetězců nad abecedou {0,1} délky 4.Nechť L = {0,1}. Napište množinu L*.Dokažte, že jazyk L = {anbncn(n ( 1} není bezkontextový.Nalezněte gramatiku, která generuje jazyk L(P), kdeP = ((q0, q1, q2(, (a, b(, (Z0, A(, (, q0, Z0, (q2()a zobrazení ( je definované takto:((q0, a, Z0) = ((q1, AZ0)((( q0, a, A) = ((q1, AA)((( q1, a, A) = ((q0, AA)((( q1, (, A) = ((q2, A)((( q2, b, A) = ((q2, ()(.Ukažte, že jazyky L1 a L2, L1 = (c0n1n( n ( 1( ( (0n12n( n ( 1( L2 = (w( w ( (a, b(*, w obsahuje stejný počet a i b(jsou deterministické bezkontextové jazyky.Je dána gramatika G = ((S, A(, (0, 1(, P, S) P: S(0A1 0A(00A1(001.Určete jazyk, který tato gramatika generuje.Je dána gramatika G = ({A, B}, {a, b}, P, A) P: A(aAb(( B(bbA(aaB(a(B aA(bB(b.Určete jazyk, který tato gramatika generuje.Je dána gramatika G = ({I, R, C}, {a, b, c, 0, 1, 2}, P, I) P: I(IR(IC(R R(a(b(c C(0(1(2.Určete jazyk, který tato gramatika generuje.Uvažujme gramatiku G = ((S, A, C, 1, 2, 3(, {a, b, c}, P, S)kde pravidla jsou P = P1 ( P2 (P3 P1 = {S(aAbC3, A(aAbC, A(1} P2 = {Cb(bC} P3 = {1b(b1, 1C(c2, 2C(c2, 23((}.Určete jazyk, který tato gramatika generuje.Je daný bezkontextový jazyk L=(02i0j1(11)i+1( i,j(0(. Napište bezkontextovou gramatiku v Greibachové normálním tvare, která ho generuje. Rozhodněte či je L regulární jazyk.Napište gramatiku, která generuje jazyk a(ab(. Použijte výlučně pravidla tvaru A((BxC anebo A((w, kde A,B,C jsou neterminální symboly, x je terminální písmeno a w je terminální slovo.Určete jazyk daný gramatikou S((AA, A((a ((.Napište libovolnou gramatiku, která generuje jazyk L={a6,a99}. Určete L(G) pro gramatiku G s pravidly S ( AAb AA ( A( aa) Gramatika G z předešlého bodu je ........................(uveďte typ podle Chomského hierarchie).b) Odvoďte některé slovo v gramatice G.c) Jazyk L(G) z bodu 6 je /není konečný? (Konečný jazyk obsahuje konečnou množinu slov)Odvození S ((aBaa ( abaa je / není odvozením v regulární gramatice. Zdůvodněte.Napište příklad gramatiky (t.j. pravidla gramatiky), v kteréj je možné převést odvození XZ (( aXZaabB.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.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(. Rozhodněte zda platí 1(11)(1 =1((11)(.Bezkontextové gramatikyNavrhněte bezkontextovou gramatiku, která generuje jazyk L = (ai+2b4i+1: i ( 0(Napište bezkontextovou gramatiku, která generuje jazyk L = (ai+2b4i: i ( 0(.Napište bezkontextovou gramatiku, která generuje jazyk L = (aicjb2i+1: i, j( 1(.Zapište odvození slova a2cb5 v navrhnuté gramatice a nakreslete strom odvození.Zapište algoritmus, který k dané bezkontextové gramatice vytvoří ekvivalentní gramatiku bez ( pravidel. Dokažte správnost algoritmu.Ilustrujte práci algoritmu na gramatice:A(aA(BB(bB(CC(cC((Je dána bezkontextová gramatikaS(aaA(bB(cbbaA(ab(B(abbAB(cbc(aB(bAodvoďte 3 slova z L(G)Uveďte 3 slova nepatřící do L(G). Zdůvodněte.Ke slovům z bodu (a) nakreslete strom odvozeníNapište bezkontextovou gramatiku, která generuje jazykL = (a2ibi+1: i ( 0( Odvoďte v ní slovo a2b2 a nakreslete strom odvození pro slovo a8b5.Napište bezkontextovou gramatiku, která generuje jazykL = (ai+2b3jc1+jd5+2i: i, j ( 0(Nechť G = (N, T, P, S) je bezkontextová gramatika a (1, (2 řetězce, přičemž (1, (2 ( (N ( T)*. Navrhněte algoritmus, kterým je možné zjistit, zda platí (1 (G* (2.Napište bezkontextovou gramatiku, která generuje jazykL= { a2b3jc1+jd2i : i,j > 0 }.Je daný bezkontextový jazyk L=(1iw1i+1( w((0,1((, i(0(. Zadejte bezkontextovou gramatiku a) v Chomského normálním tvarub) v Greibachové normálním tvaru která ho generuje.Napište bezkontextovou gramatiku, která generuje jazyk L= (abaa((((ai(ba)2i(1 : i ( 1 (.Zapište algoritmus, který k dané bezkontextové gramatice vytvoří ekvivalentní gramatiku bez pravidel typu A( B, A,B ( N.Ilustrujte práci algoritmu na gramatice:A ( aA ( BB ( bB ( CC ( cC ( cJe daný bezkontextový jazyk L=(1i21i+1( i(0(. Zadejte bezkontextovou gramatiku a) v Chomského normálním tvareb) v Greibachové normálním tvare která ho generuje.Zadejte 3 bezkontextové gramatiky obsahujíce (-pravidla a pravidla typu A(B.Sestrojte k nim ekvivalentní gramatikya) bez ( pravidel.b) bez pravidel typu A(B.c) v Chomského normálním tvare.d) v Greibachové normálním tvare.Daná je gramatika G = ({E, T, F}, {+, (, 3, 5, 6}, P, E)P: E(E+T(T T(T(F(F F(3(5(6.Vytvořte odvození řetězce 5+6(3.Mějme gramatiku G s počátečním symbolem S a přepisujícími pravidly P:S(aABc((A(cSB(AbB(bB(a.Pro řetězec acabac vytvořte levé a pravé odvození.Daná je gramatikaG = ({S}, {a, b, if, then, else}, P, S)P: S(if b then S else S S(if b then S S(aVytvořte jednoznačnou gramatiku G´ ekvivalentní s gramatikou G.Mějme gramatiku G = ({A, B, C, D}, {a, b, c}, P, A),kde P obsahuje pravidlaA(aBc(CCB(Bcb(DBC(Cc(aD(DBD((.Vypočtěte množinu nadbytečných symbolů N.Mějme gramatiku G = ({A, B, C, D,E}, {a, b, c}, P, A),kde P obsahuje pravidlaA(aC(EbB(DD(Bb(cC(E(bD(aC(BbE(aAb(bVypočtěte množinu dostupných symbolů V.Mějme gramatiku s pravidlyA(CBA(aB(b((C(c((.Vytvořte odvození této gramatiky.Daná je gramatikaG = ({S, A, B}, {a, b}, P, S),která má pravidlaS(ba(aBA(a(aS(bAAB(b(bS(aBB.Ukažte, že tato gramatika je víceznačná (vezměte např. větu aabbab). Vytvořte ekvivalentní jednoznačnou gramatiku.Gramatiku s pravidlyS(A(BA(aB(bS(bB(AB(bAC(AS(btransformujte na ekvivalentní gramatiku bez nadbytečných symbolů.Ke gramaticeS(A(BA(C(DB( D(EC(S(a((D(S(bE(S(c((najděte ekvivalentní vlastní gramatiku.V gramaticeS(ABA(BS(bB(SA(aodstraňte levou rekurzi.Je daná bezkontextová gramatika G = ((S, A(, (a, b, c(, P, S),kde množina P obsahuje tyto pravidla:S(aAScA(aS(bA(cSAb.Odvoďte levou derivaci pro větu acbabbc.Uvažujme bezkontextovou gramatiku G = ({S, T, F}, {a, (, ), +, *}, P, S)kde P: S(T S(S+T T(F T(F*T F(a F((S).Vytvořte derivační strom pro větu a + aBuď G = (N, {a}, P, S), N = {A, B, S}, P = {S(a, S(A, A(AB, B(a}bezkontextová gramatika. Sestrojte k ní ekvivalentní redukovanou gramatiku.BuďA = ({q0, q1, q2}, {a, b}, {Z0, A}, (, q0, Z0, {q2})((q0, a, Z0) = {(q1, AZ0)}((q0, a, A) = {(q1, AA)}((q1, a, A) = {(q0, AA)}((q1, (, A) = {(q2, A)}((q2, b, A) = {(q2, ()}zásobníkový automat. Nalezněte vlastní bezkontextovou gramatiku G tak, že L(G) = L(A).Napište bezkontextovou gramatiku, která generuje jazyk L= (abc(((ai(ba)2i(1 : i ( 1 (.Napište algoritmus, který k dané bezkontextové gramatice G vytvoří gramatiku G´ bez pravidel A( B pro kterou platí L(G)=L(G´).Napište bezkontextovou gramatiku, která generuje jazyk L= (abaa((((ai(ba)2i(1 : i ( 1 (.Je daný bezkontextový jazyk L=(1iw1i+1( w((0,1((˝, i(0(. Zadejte bezkontextovou gramatiku a) v Chomského normálním tvareb) v Greibachové normálním tvarekterá ho generuje.Napište bezkontextovou gramatiku, která generuje jazyk L= (aba(((ai(ba)2i(1 : i ( 1 (.Je daný bezkontextový jazyk L=(1i21i+2( i(0(. Zadejte bezkontextovou gramatiku pro tento jazyk.Kontextové gramatiky1. Pro kontextovou gramatiku s pravidlyAA(AaAB(cBB(bB proveďte jeden krok odvozeníAABB(Regulární gramatikySestrojte regulární gramatiku, která generuje právě ty slova nad abecedouA = {a,b}, v kterých se před každým výskytem písmena a vyskytuje slovo bbb.Je daný regulární jazyk L= 0(1(0)(1. Sestrojte deterministický konečný automat, který ho rozpoznává.Sestrojte regulární gramatiku, která ho generuje.Ukažte, že jazyk, který obsahuje konečně mnoho slov je regulární.Redukované gramatikyNajděte ekvivalentní redukovanou gramatiku ke gramaticeS(ABc(AA(BBA(aB(aA(aaB(bBD(dB(ddNajděte ekvivalentní redukovanou gramatiku ke gramatice S(AB(CAA(aB(BC(ABC(aB(bNajděte ekvivalentní redukovanou gramatiku ke gramaticeS(XYX(ZXX(aY(YZ(bYZ(aY(bNajděte ekvivalentní redukovanou gramatiku ke gramaticeS(XYc(XX(YYX(aY(aX(aaY(bYbZ(aZZ(bSestrojte redukovanou gramatiku ke gramaticeA(aAb(aAC(a(bBaB(bCa(ACC(bCB(AB6. Určete pravidla umožňující v regulární gramatice odvozeníaB(* aabcCPřeveďte bezkontextovou gramatiku G = ({S, A, B}, {a, b}, P, S)P: S(A S(B A(aB A(bS A(b B(AB B(Ba B(AS B(bna ekvivalentní redukovanou bezkontextovou gramatiku.Bez (-pravidelPřetransformujte do ekvivalentní gramatiky bez (-pravidelS(AAa(BBbA(aaB(AA((B(bbA(BB((Přetransformujte do ekvivalentní gramatiky bez (-pravidelS(ABCA(Ab(BCB(bB(b(Ab((C(cC(c(Ac((Zapište algoritmus, který k dané bezkontextové gramatice vytvoří ekvivalentní gramatiku bez ( pravidel. Dokažte správnost algoritmu.Ilustrujte práci algoritmu na gramatice:A(aA(BB(bB(CC(cC((Ke gramatice S(bAA(a1Aa2Aa3Aa4((najděte ekvivalentní gramatiku bez ( pravidel.Najděte gramatiku bez ( pravidel, která je ekvivalentní s gramatikouS(ABCA(BB(eB(CC(aC(AA(bKe gramatice S ----bA
A ----a1 A a2 A a3 A a 4najděte ekvivalentní gramatiku bez ( pravidel.Gramatiku G = ({S, A, B, C}, {a, b, c}, P, S) s pravidlyS(AaBb(aCa(AC A(BC(a(( B(Bb(b C(cC(S((transformujte na gramatiku bez (-pravidel.Mějme gramatiku s pravidly A(CBA(a B(b(( C(c((.Odstraňte (-pravidla.Uvažujme bezkontextovou gramatiku G = ({S}, {0, 1}, {S(0S1S, S((}, S)Sestrojte k ní ekvivalentní bezkontextovou gramatiku G = (N1, {0, 1}, P1, S1)bez (-pravidel.Sestrojte k dané bezkontextové gramatice ekvivalentní gramatiku bez ( pravidel. A ( aA ( cBBB ( bB ( CCC ( cC ( (Je daný bezkontextový jazyk L=(02i1(11)i+1( i,j(0(. Napište bezkontextovou gramatiku v Chomského normálním tvare, která ho generuje.CHNT gramatikyPřeveďte do CHNT gramatiku S(aS(aSbS((Převeďte do CHNT gramatikuS(0B(1A((B(1(0BBA(0(1AAGramatika je v Chomského normálním tvaru (CHNT), když má pravidla tvaru A(BC anebo A(a, kde A, B, C ( N, a ( T.Sestrojte gramatiku v CHNT pro jazyk L = (a8( Nakreslete strom odvození slova a8Sestrojte gramatiku v CHNT ekvivalentní ke gramatice:S(aSASb(Saa(bA(caA(Ac(bcaNa Chomského normální tvar upravte gramatikuG = ((S, T, L(, (a, b, +, -, *, /, (, ((, P, S) kde P obsahuje pravidlaS(T+S(T-S(TT(L*T(L/T(LL((S((a(bNapište gramatiku v Chomského normálním tvaru pro jazyk L= (a8(.Na CHNT upravte gramatiku pro aritmetický výrazE(E+T(TT(T*F(FF((E)(a.Buď G = ({S, A, B}, {a, b}, P, S)P: S(aB S(bA A(aS A(bAA A(a B(bS B(aBB B(bbezkontextová gramatika. Převeďte ji do Chomského normální formy.GNT gramatikyUpravte na ekvivalentní gramatiku v GNTS(SaScbPřeveďte danou gramatiku na ekvivalentní gramatiku v Greibachové normálním tvaru A(AAb(aNačrtněte strom odvození slova aabaabb v původní i nové gramatice.Navrhněte gramatiku v Greibachové binárním tvaru, která generuje jazyk L*, pro L = (an+1b2n: n ( 1(Sestrojte gramatiku v Greibachovém normálním tvaru generující jazykL = (wwR(w ( (a, b(*( GramatikuG = ((S, A, B(, (a, b(, P, S) s pravidlyS(Ba(AbA(Sa(AAb(aB(Sb(BBa(b upravte na Greibachové normální tvar.Je daný bezkontextový jazyk L=(01i0i1( w((0,1((, i(0(. Zadejte bezkontextovou gramatiku v Greibachové normálním tvaru která ho generuje.t - gramatikya) Definujte gramatiku s ohraničenou pozicí typu t.b) Daný je jazyk L = (a2ibi(i (0(. Určete pozičně ohraničenou gramatiku G1 typu (0,0,2), G2 typu (0,2,0) a G3 typu (2,0,0), tak, aby L(G1) = L(G2) = L(G3) = L.Daný je jazyk L= (a i b 4i ( i ( 0 (. Určete pozičně ohraničenou gramatiku G1 typu(0,0,0(, G2 typu ( 0,3,0( a G3 typu (2,0,0(, tak, aby L(G1 ( = L(G2 (= L(G3( = L.Parikhův vektorUrčete množiny Parikhových vektorů jazyka L = (aba)*.Určete množinu Parikhových vektorů jazyka generovaného gramatikouS(aS(aAA(bbAa(c Zadejte regulární jazyk se stejnou množinou Parikhových vektorů.Pumpovací větaUkažte, že jazyk L = (ab)*c splňuje požadavky Pumpovací věty.Vyslovte Pumpovací lemmu pro bezkontextové gramatiky.Určete hodnoty konstant vyskytujících se v lemmě pro jazykyL1 = (a3nbn(n ( 1(L2 = (bn(n ( 100(L3 = (a3nbn(n ( 1( ( (c400(Vyslovte Pumpovací lemu pro regulární gramatiku. Dokažte, že jazykL= {aibi: i > 0 } není regulární.Zvolte 3 regulární jazyky a 3 bezkontextové jazyky. Ukažte, že splňují Pumpovací větu pro regulární resp. bezkontextové jazyky, uveďte hodnoty konstant p,q z příslušné Pumpovací věty. Vyhovují i jiné hodnoty konstant jako ty, co jste navrhli? Uveďte 2 příklady jazyků, které nejsou bezkontextové ne
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 2024 unium.cz