1. Gramatyki i języki – zadania



Pobieranie 24.99 Kb.
Data28.04.2016
Rozmiar24.99 Kb.
1. Gramatyki i języki – zadania
Podać, jakie języki są generowane przez poniższe gramatyki. (Wielkie litery łacińskie oznaczają symbole nieterminalne, małe litery łacińskie, cyfry oraz znaki specjalne, jak np. nawiasy okrągłe lub kwadratowe, oznaczają symbole terminalne, symbolem początkowym jest nieterminal stojący w lewej stronie pierwszej produkcji.)
1.1.
S    aS  |  bS  | aA

A    aA  |  bA | aB 


B    aB | bB | 
1.2.
S    aS  |  bS  | aA

A    aB   

B    aB | bB | 
1.3.
S    aS  |  bS  | aA

A    aB  | bB 

B    
1.4.
S    aA

A    baA | aA | ba |  a 
1.5.
S    SAB | AB

A    Aa | a   

B    Bb | b   
1.6.
S    ABC

A    aAb | ab   

B    bBa | ba

C    aCb | ab
1.7.
S    AC

A    aAb | aBb   

B    bBa | ba

C    aCb | ab
1.8.
S    aAb | aSa

A    bAcc | ab   
1.9.
S    aSb  |  aAb

A    bAa | bBa   

B    aBb | ab
1.10.
S    aaSb | bAa

A    aAbb | ba   
Jakie języki są generowane przez poniższe gramatyki bezkontekstowe? Czy poniższe gramatyki są jednoznaczne? Uzasadnić.
1.11

S    AB | DC

A    aA |    

B    bBc |    

C    cC |    

D    aDb |    
1.12.

S    A | CD

A    aAd | B   

B    bBc |    

C    aCb |    

D    cDd |    
1.13.

E  E+E | E*E | (E) | a

Podać, jakie języki są generowane przez poniższe gramatyki. (Wielkie litery łacińskie oznaczają symbole nieterminalne, małe litery łacińskie, cyfry oraz znaki specjalne, jak np. nawiasy okrągłe lub kwadratowe, oznaczają symbole terminalne, symbolem początkowym jest nieterminal stojący w lewej stronie pierwszej produkcji.)


1.14.

S  bAb
A  aAb | acb

1.15.

S  aS | aSb | 
1.16.

S  SS | aSb | bSa | ab | ba
1.17.

S  SAB | ABS | aabb
A  Aaa | aa
B  Bbb | bb

1.18.

S  bSa | aSb | 
1.19.

S  aSa | bSb | aa | bb
1.20.

S  SS | ab | ba
1.21.

S  Sa | Aa
A  aAb | ab

1.22.

S  SA | SB | 
A  Aa | a
B  Bb | b

1.23.

S  abcc | aSc | aAc
A  bAc | bc

1.24.

S  A | B | C
A  ab | aaaA
B  bbc | bbbB
C  ccca | cccC

1.25.

S  a | ab | abc | abcS
1.26.

S  aA
A  baA | aA | ba | a

1.27.

S  abb | abbA
A  aab | aabS

1.28.

S  SS | aSb | ab
1.29.

S  A | B
A  a | ab | abA
B  b | ba | ba

1.30.

S  SS | (S) | 
1.31.

S  SS | [S] | A
A  AA | (A) | 

1.32.

S S S | (1 S )1 | (2 S )2 | (3 S )3 |
gdzie: T = { (1, )1, (2, )2, (3, )3 }
1.33.

S  Sa | Sb | 

1.34.

S  aSa | bAb
A  cAc | bab

1.35.

S  aSb | bAc
A  Ac | cb

1.36.

S  aAbBc
A  bAa | ba


B  cBb | cb


©absta.pl 2016
wyślij wiadomość

    Strona główna