6. Przekształcenia gramatyk bezkontekstowych – odpowiedzi 1



Pobieranie 27.1 Kb.
Data28.04.2016
Rozmiar27.1 Kb.
6. Przekształcenia gramatyk bezkontekstowych – odpowiedzi
6.1.

Brak symboli nieużytecznych i nieosiągalnych.

Po usunięciu ε-produkcji:

S  aAA | aA | a | B

A  b

B  BAa | Ba | S



Po usunięciu produkcji łańcuchowych i cykli:

S  aAA | aA | a | BAa | Ba

A  b

B  aAA | aA | a | BAa | Ba


6.2.

Brak symboli nieużytecznych i nieosiągalnych.

Po usunięciu ε-produkcji:

S  bBB | bB | b | A

A  S | a

B  AB | A

Po usunięciu produkcji łańcuchowych i cykli:

S  bBB | bB | b | a

A  bBB | bB | b | a

B  bBB | bB | b | a | AB


6.3.

Brak symboli nieużytecznych i nieosiągalnych.

Po usunięciu ε-produkcji:

S’  S | ε

S  ABS | AB | AS | BS | A | B

A  aA | a | BB | B

B  Bab | ab | A

Po usunięciu produkcji łańcuchowych i cykli:

S’  ε | ABS | AB | AS | BS | aA | a | BB | Bab | ab

S  ABS | AB | AS | BS | aA | a | BB | Bab | ab

A  aA | a | BB | Bab | ab

B  aA | a | BB | Bab | ab


6.4.

Brak symboli nieużytecznych i nieosiągalnych.

Po usunięciu ε-produkcji:

S  aBB | aB | a | SAb | Sb

A  B | AA | a

B  A


Po usunięciu produkcji łańcuchowych i cykli:

S  aBB | aB | a | SAb | Sb

A  AA | a

B  AA | a


6.5.

Brak symboli nieużytecznych i nieosiągalnych.

Po usunięciu ε-produkcji:

S’  S | 

S  ab | SS | AB

A  B | Sa | a

B  A | Sb | b

Po usunięciu produkcji łańcuchowych i cykli:

S’   | ab | SS | AB

S  ab | SS | AB

A  Sa | a | Sb | b

B  Sa | a | Sb | b


6.6.

Początkowo brak symboli nieużytecznych i nieosiągalnych.

Po usunięciu ε-produkcji:

S’  S | 

S  AB | A | B | BA | SS

A  B


B  A

Po usunięciu produkcji łańcuchowych i cykli:

S’   | AB | BA | SS

S  AB | BA | SS

Po końcowym usunięciu symboli nieużytecznych:

S’  
6.7.

Brak symboli nieużytecznych i nieosiągalnych.

Po usunięciu ε-produkcji:

S  AaBb | Aab | aBb | ab

A  Sb


B  Sa

Brak cykli.


6.8.

Brak symboli nieużytecznych i nieosiągalnych.

Po usunięciu ε-produkcji:

S’  S | ε

S  aAbB | aAb | abB | ab | AB | A | B

A  B | Sa | a

B  AB | A

Po usunięciu produkcji łańcuchowych i cykli:

S’  ε | aAbB | aAb | abB | ab | Sa | a | AB

S  aAbB | aAb | abB | ab | Sa | a | AB

A  Sa | a | AB

B  Sa | a | AB


6.9.

S  AbS’ | BaS’

S’  ABS’ | ε

A  Bba | a

B  aabB’ | bB’

B’  baabB’ | ε


6.10.

S  AbS’ | BaS’

S’  BAS’ | ε

A  BaS’baA’ | bA’

A’  bS’baA’ | ε

B  bA’bS’abB’ | aB’

B’  aS’abB’ | aS’baA’bS’abB’ | ε
6.11.

S  ABS’ | BAS’

S’  aaS’ | ε

A  Ba | b

B  bbB’ | aB’

B’  abB’ | ε


6.12.

S  AAaS’ | BBbS’

S’  SS’ | ε

A  BBbS’AA’ | aA’

A’  AaS’AA’ | ε

B  aA’AaS’BB’ | bB’

B’  BbS’BB’ | BbS’AA’AaS’BB’ | ε
6.13.

S  ASa | BSb | ba

A  BaA | b

B  bbB’ | aB’

B’  bB’ | aAbB’ | ε
6.14.

S  ABa | BaB

A  BaBaAA’ | bA’

A’  BaaAA’ | ε

B  bA’BabBB’ | aB’

B’  aBaAA’BabBB’ | aBbBB’ | ε


6.15.

S  AS’ | BS’

S’  abSS’ | ε

A  bA’


A’  AA’ | ε

B  aB’


B’  BB’ | ε
6.16.

S  CaD1 | CaD2

A  CbD3 | CaCb

Ca  a

Cb  b

Cc  c

D1  ACb

D2  SCa

D3  ACc
6.17.

S  CaD1 | CbD3

A  CaD4 | a

Ca  a

Cb  b

D1  CaD2

D2  SCb

D3  ACa

D4  AD5

D5  CbCb


6.18.

Po usunięciu lewostronnej rekursji:

S  AB | BS

A  BA | a

B  aSB' | bB' | aS | b

B'  ASB' | AS

Ostatecznie:

S  aSB'AB | bB'AB | aSAB | bAB | aB | aSB'S | bB'S | aSS | bS

A  aSB'A | bB'A | aSA | bA | a

B  aSB' | bB' | aS | b

B'  aSB'ASB' | bB'ASB' | aSASB' | bASB' | aSB' | aSB'AS | bB'AS | aSAS | bAS | aS
6.19.

Po usunięciu lewostronnej rekursji:

S  bS' | b

S'  AS' | A

A  BA | a

B  bS'BB' | bBB' | aBB' | bS'B | bB | aB

B'  ABB' | AB

Ostatecznie:

S  bS' | b

S'  bS'BB'AS' | bBB'AS' | aBB'AS' | bS'BAS' | bBAS' | aBAS' | aS' | bS'BB'A | bBB'A | aBB'A | bS'BA | bBA | aBA | a

A  bS'BB'A | bBB'A | aBB'A | bS'BA | bBA | aBA | a

B  bS'BB' | bBB' | aBB' | bS'B | bB | aB



B'  bS'BB'ABB' | bBB'ABB' | aBB'ABB' | bS'BABB' | bBABB' | aBABB' | aBB' | bS'BB'AB | bBB'AB | aBB'AB | bS'BAB | bBAB | aBAB | aB

Pobieranie 27.1 Kb.





©absta.pl 2020
wyślij wiadomość

    Strona główna