index
předchozí
1
2
3
4
5
6
7
8
9
10
11
12
následující
Cvičení první
Formální gramatiky - Regulární gramatiky
1) Jsou dané jazyky L1, L2 nad abecedou {x,y,z} L1 = {xy,y,yx}, L2 = {y,z}.
- L1 sjednoceno L2
- L1 průnik L2
- L1 . L2 , L2 . L1
- L20 , L21 , L22 ,
L23 , L2* , L2+
2) Rozhodněte zda platí
- Li = { wi | w náleží L}
- w náleží Li => |w|=i
3) Porovnejte (slovně popište) jazyky a rozhodněte zda L1 = L4 (DÚ)
- L1 = {x,y,z}*
- L2 = {xyz}*
- L3 = {x}* . {y}* . {z}*
- L4 = ({x}* . {y}* . {z}*)*
- L5 = ({x,y}* sjednoceno {z}*)*
- L6 = {x,y,z}* . {x} . {x,y,z}*
4) Pomocí jazyků L1={a}, L2={b} a množinových operací sjednocení,
průniku, konkatenace, iterace (*,+) a doplňku vyjádřete jazyk,
- (i) jehož slova obsahují alespoň 2 znaky 'a'
- (ii) jehož slova mají sudou délku
- (iii) jehož slova začínají znakem 'a' a končí znakem 'b'
- (iv) jehož slova splňují (ii) a (iii)
- (v) jehož slova nesplňují (ii)
5) Dokažte zda pro libovolné jazyky L1,2,3 platí, nebo neplatí:
- L1 podmnožinou L1 . L2
- (L1 sjednoceno L2) . L3 = (L1 . L3) sjednoceno (L2 . L3)
- (L1 průnik L2) . L3 = (L1 . L3) průnik (L2 . L3)
- L1i . L2i = (L1 . L2)i
- L1* sjednoceno L2i = (L1 sjednoceno L2)*
- L1* . L1* = L1*
- (L1 sjednoceno L2)* = (L1* . L2 . (L1)*)*
6) Jaký jazyk generuje gramatika G=({S,A},{a,b,c},P,S) a jakého je typu?
S => bS | cS | aA
A => aA | bA | cA | epsilon
7) Navrhněte regulární gramatiky pro následující jazyky:
- L1 = {a,b,c,d}*
- L1 = {a,b,c,d}i{a,b,c,d}* ; i=2,10,100
- L2 = { w | w náleží {a,b}*, |w|>=3 }
- L3 = { w | w náleží {a,b}*, |w|=3k, k>=0 }
8) Jaký jazyk generuje následující gramatika?
Diskutujte vhodnost označení neterminálů (třeba S00,
S01,S10,S11).
S => aS | bB | epsilon
A => aS | bC
B => aC | bS
C => aB | bA
9) Navrhněte regulární gramatiku pro jazyk
- L = { w | w náleží {a,b,c}*, w obsahuje podslovo 'abb'}
- L = { w.wR | w náleží {a,b}* }
- L = { w | w náleží {a,b,c}*, první 3 znaky w = poslední 3 znaky w } (DÚ)
- L = { w | w náleží {a,b,c}*, w neobsahuje podslovo 'abb' } (DÚ)
- L = { w | w náleží {a,b,c}*, #a(w) = 2k, #b(w) = 3l+1, k,l >= 0} (DÚ)
- L = { w | w náleží {0,1,..,9}*, w je zápis přirozeného čísla dělitelného 5} (DÚ)
- L = { w | w náleží {0,1,..,9}*, w je zápis přirozeného čísla dělitelného 3} (DÚ)
- L = { w | w náleží {0,1,..,9}*, w je zápis přirozeného čísla dělitelného 25} (DÚ)