6. Przekształcenia gramatyk bezkontekstowych – zadania



Pobieranie 13.92 Kb.
Data28.04.2016
Rozmiar13.92 Kb.
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


©absta.pl 2016
wyślij wiadomość

    Strona główna