Domácí úkol č. 1
Příklad 1 (4 body)
Pomocí jazyků L1 = {a}, L2 = {b} a množinových operací ∪, ∩, ·, iterace
(*,+) a doplňku (co–) vyjádřete jazyk slov nad abecedou {a, b}, které neobsahují
podslovo abba nebo jejich délka není dělitelná čtyřmi.
Příklad 2 (5 bodů)
Buď dána gramatika G = ({S, C}, {a, b, c}, P, S) s pravidly P = {
S → ε | abSCS | baSCS | aaSCS | bbSCS | acS | bcS | caS | cbS
C → cc }
Určete, jakého typu je gramatika G dle Chomského hierarchie gramatik. Následně
přesně popište jazyk L(G).
Příklad 3 (5 bodů)
Navrhněte regulární gramatiku pro jazyk všech slov nad abecedou {a, b}, jejichž
délka je větší než jedna a počet symbolů b je lichý.
Příklad 4 (6 bodů)
1. Udejte příklad gramatiky G, která je regulární a generuje nekonečný jazyk.
2. Udejte příklad gramatiky G tak, aby G byla bezkontextová, G nebyla
regulární a přitom L(G) byl konečný.
3. Udejte příklad dvou gramatik G1, G2 takových, že L(G1) = L(G2) a přitom
G1 je regulární a G2 bezkontextová.
Své řešení v každém bodě vysvětlete.
1