| 6. Przekształcenia gramatyk bezkontekstowych – zadania
Poniższe gramatyki doprowadzić do postaci prawidłowej:
6.1.
S aAA | B
A b |
B BAa | S
6.2.
S bBB | A
A S | a
B AB |
6.3.
S ABS | B
A aA | BB |
B Bab | A
6.4.
S aBB | SAb
A B | AA | a
B A |
6.5.
S ab | SS | AB |
A B | Sa
B A | Sb
6.6.
S AB | BA | SS
A B |
B A |
6.7.
S AaBb | ab
A Sb |
B Sa |
6.8.
S aAbB | AB
A B | Sa
B AB |
Usunąć lewostronną rekursję w poniższych gramatykach:
6.9.
S SAB | Ab | Ba
A Bba | a
B Aab | b
6.10.
S SBA | Ba | Ab
A Sba | b
B Sab | a
6.11.
S Saa | AB | BA
A Ba | b
B Ab | a
6.12.
S AAa | BBb | SS
A SA | a
B SB | b
6.13.
S ASa | BSb | ba
A BaA | b
B a | Bb | Ab
6.14.
S ABa | BaB
A SaA | b
B SbB | a
6.15.
S A | B | SabS
A AA | b
B BB | a
Poniższe gramatyki bezkontekstowe przekształcić do postaci normalnej Chomsky'ego.
6.16.
S aAb | aSa
A bAc | ab
6.17.
S aaSb | bAa
A aAbb | a
Poniższe gramatyki bezkontekstowe przekształcić do postaci normalnej Greibach.
6.18.
S AB | BS
A BA | a
B AS | b
6.19.
S SA | b
A BA | a
B SB | AB
| 
