1. do postaci monotonicznej
S->AB|ASA|DC|Lambda
A->CA|0
B->1C|1
C->CA|CC
D->DA|1
2. Hierarchia Chomskiego
3. L =|a*b*c| wyznaczyc produkcje i narysowac graf
4. do postaci greibach
A->BA|Aa|AB|a
B->BA|BB|b
5. Graf moora i wyzznaczyc R31
abc
1|212|X
2|213|Y
3|322|Z
1. automat ze stosem :
(a,g0,#)-->(g1,w)
(a,g1,w)-->(g1,ww)
(c,g1,w)-->(g1,ww)
(b,g1,w)-->(g2,lambda)
(b,g2,w)-->(g2,lambda)
(d,g1,w)-->(g2,lambda)
(b,g2,w)-->(g2,lambda)
(lambda,g2,w)-->(g2,lambda)
sprawdzić czy automat wygeneruje słowo "accdba"
2. doprowadzić do postaci detrministycznej- podać reguły produkcji i narysować wykres:
S-->wX|wY|zX
X-->zY
Y-->wX|lambda
3. Jaki język generuje gramatyka:
S-->RSR|rW
R-->t
Y-->Rw|r|lambda
4. Podać wyrażenie regularne dla L={w należy do (a,b)* | słowo ma dokładnie 2 litery b} i narysować wykres
5. Znaleźć gramatykę bezkontekstową i wyrażenie regularne dla L={aba,aab,bbabb,ababab,baaabbb,bbbbbb}
1. Jaki język generuje gramatyka
S -> Aa | BSB
A -> AA | b | c
B -> ba | b
2.
L = |a*(b+bc)*d*|
3. CYK
x=12133
S -> SD | BD
A -> 1 | DD
B -> AC | 3D
C -> 2 | CA
D -> 3 | DD
4. monotonicznosc
S -> CB | SC | lambda
A -> 0 | BA
B -> 1 | 0B
C -> CC | 10
5.
a) uklad rownan z ktorego mozna wyliczyc T12
b) obliczyc T12
S\We a b c Wy
1 1 3 2 X
2 1 1 2 Y
3 3 2 3 Z
1. Wyznaczyć g. regularną:
|a*b*c + d*|
S -> aA | bB | cC | dD
A -> aA | bB | cC
B -> bB | cC
C -> lambda
D -> dD | lambda
(Zapodaj ktoś tą stronke z rysowaniem tych grafów, to dodam)
2. CYK:
x=12213
(już przekształcone tj. 2D -> ED, E -> 2)
S -> SD | BD
A -> CC | 1
B -> AC | ED
C -> CA | 2
D -> AD | 3
E -> 2
_________________
| A |C,E|C,E| A | D |
| B | A | C | D |
|(-)| A | B |
|(-)| D |
| D |
nie produkuje!
3.
a) Podać wyrażenie regularne dla L={w należy do (a,b,c)* - słowo ma jedno c, a na początku, aa na końcu}
L=|a(a+b)*c(a+b)*aa|
b) Podać ile jest słówm gdy L1={L(w)=6} (siakoś tak)
L1={
acaaaa, aacaaa, aaacaa
acabaa, aacbaa, aabcaa
acbaaa, abcaaa, abacaa
acbbaa, abcbaa, abbcaa }
4. Meal'y
| 1 2 3 |
1|1/1 3/1 1 |
2| 3 2 3 |
3| 1 3/1 2 |
{ R31 = 1R11 + 2R31 + 3R21 + 2
{ R11 = 1R11 + 2R31 + 3R11 + 1 + 2
{ R21 = 1R31 + 2R21 + 3R31
R31 = (11*2 + 13*2 + 2 + 32*1 + 32*1 + 32*3)*(11*1 + 11*2 + 13*1 + 13*2 + 2)
5. Doprowadzić do postaci deterministycznej
S -> wX | wY | zX
X -> zY | wX
Y -> wY | z