• Non ci sono risultati.

G G Data una Grammatica ed una Stringa verificare che la Stringa sia generata dalla Grammatica: 1. Esercitazione I

N/A
N/A
Protected

Academic year: 2021

Condividi "G G Data una Grammatica ed una Stringa verificare che la Stringa sia generata dalla Grammatica: 1. Esercitazione I"

Copied!
6
0
0

Testo completo

(1)

GRAMMATICHE GENERATRICI

Data una Grammatica ed una Stringa verificare che la Stringa sia generata dalla Grammatica:

1.

SA ScSc A aa|bb

s= ccccbbcccc

2.

SA ScSc A aa|bb

s= ccaabbcc

3. S  Sa | cAb A  aA | bBc B  cSb | b

s=caabbcbaa

4. S  aS | CbC C  cC | c | S

s=aaaccbaaccc

5.

START “inizio” START “fine”|CORPO CORPO PARTE1 PARTE2

PARTE1 “atomo1” PARTE1| ε

PARTE2 “atomo2”| “atomo2” PARTE2

s="inizio" "inizio" "atomo1" "atomo1" "atomo2" "atomo2" "fine" "fine"

6.

START “inizio” START “fine”|CORPO CORPO PARTE1 PARTE2

PARTE1 “atomo1” PARTE1| ε

PARTE2 “atomo2”| “atomo2” PARTE2

I

(2)

s="inizio" "atomo1" "atomo2" "atomo2" "fine" "fine"

7.

START “inizio” START “fine”|CORPO CORPO PARTE1 PARTE2

PARTE1 “atomo1” PARTE1| ε

PARTE2 “atomo2”| “atomo2” PARTE2

s="inizio" "atomo1" "atomo2" "atomo1" "fine"

8. S  V | D V  aaV | b D  b | aDb

s= aaaab

9. S  V | D V  aaV | b D  b | aDb

s= aaabbb

10. S  V | D V  aaV | b D  b | aDb

s= abb

Data la Grammatica individuare il Linguaggio generato:

11. S  aS | B B  bB | bC C  cC | c

12. S  aSc | B B  bB | b

13. S  aSb|ab

14. S  aAb aA  aaAb A  ε

15. S  AS | A A  aAb | ab

16. S  Ab A  Sa

(3)

17. S  aSc | A A  bAc| ε

(4)

SOLUZIONI

Data una Grammatica ed una Stringa verificare che la Stringa sia generata dalla Grammatica:

1.

SA ScSc A aa|bb

s= ccccbbcccc

cSc ccScc cccSccc ccccScccc ccccAcccc ccccbbcccc

2.

SA ScSc A aa|bb

s= ccaabbcc

cSc ccScc

ccAcc  NO : ccaacc | ccbbcc

3. S -> Sa | cAb A -> aA | bBc B -> cSb | b

s=caabbcbaa

Sa Saa cAbaa caAbaa caaAbaa caabBcbaa caabbcbaa

4. S  aS | CbC C  cC | c | S

(5)

s=aaaccbaaccc

aS aaS aaaS aaaCbC aaacCbC aaaccbC aaaccbS aaaccbaS aaaccbaaS aaaccbaa?  NO

5.

START “inizio” START “fine”|CORPO CORPO PARTE1 PARTE2

PARTE1 “atomo1” PARTE1| ε

PARTE2 “atomo2”| “atomo2” PARTE2

s="inizio" "inizio" "atomo1" "atomo1" "atomo2" "atomo2" "fine" "fine"

“inizio” START “fine”

“inizio” “inizio” START “fine” “fine”

“inizio” “inizio” CORPO “fine” “fine”

“inizio” “inizio” PARTE1 PARTE2 “fine” “fine”

“inizio” “inizio” “atomo1” PARTE1 PARTE2 “fine” “fine”

“inizio” “inizio” “atomo1” “atomo1” PARTE2 “fine” “fine”

“inizio” “inizio” “atomo1” “atomo1” “atomo2” PARTE2 “fine” “fine”

“inizio” “inizio” “atomo1” “atomo1” “atomo2” “atomo2” “fine” “fine”

6.

START “inizio” START “fine”|CORPO CORPO PARTE1 PARTE2

PARTE1 “atomo1” PARTE1| ε

PARTE2 “atomo2”| “atomo2” PARTE2

s="inizio" "atomo1" "atomo2" "atomo2" "fine" "fine"

“inizio” START “fine” NO : “inizio” “inizio” START “fine” “fine” | “inizio” CORPO

“fine”

7.

START “inizio” START “fine”|CORPO CORPO PARTE1 PARTE2

PARTE1 “atomo1” PARTE1| ε

PARTE2 “atomo2”| “atomo2” PARTE2

s="inizio" "atomo1" "atomo2" "atomo1" "fine"

“inizio” START “fine”

(6)

“inizio” CORPO “fine”

“inizio” PARTE1 PARTE2 “fine”

“inizio” “atomo1” PARTE1 PARTE2 “fine”

“inizio” “atomo1” PARTE2 “fine”

“inizio” “atomo1” “atomo2” PARTE2 “fine”  NO 8. S  V | D

V  aaV | b D  b | aDb

s= aaaab

V aaV aaaaV aaaab

9. S  V | D V  aaV | b D  b | aDb

s= aaabbb

D aDb aaDbb

aaaDbbb NO

10. S  V | D V  aaV | b D  b | aDb

s= abb

D aDb abb

11. {anbmcp | n>=0; m,p>0}

12. {anbmcn | n>=0, m>0}

13. {anbn | n>0}

14. {anbn | n>0}

15. {am1bm1 am2bm2 ... amkbmk | k>0, mi>0 per ogni i, 1≤i≤k}

16. {}

17. {anbmcn+m | n,m >=0}

Riferimenti

Documenti correlati

Riuscire a dimostrare che il carbonio presente nel meteorite marziano si è originato sul Pianeta rosso e non è un prodotto di contaminazione terrestre, sarebbe una

Gli studenti si addestrano, in caso di terremoto, a rifugiarsi sotto i banchi e ad affrettarsi verso un colle per sfuggire agli tsunami. Dopo la scossa verrà

 Alla proiezione di quel film hanno assistito anche alcuni studenti, i quali lo hanno molto apprezzato.. Completa le seguenti frasi inserendo negli spazi i pronomi personali “le”

a) Sottolinea i pronomi presenti nelle seguenti frasi: Punti ... /10.  Io non parteciperò alla gita scolastica che si svolgerà il

[r]

Compila la tabella scrivendo la prima persona singolare dei tempi semplici e composti del congiuntivo:.. VERBO PRESENTE PASSATO

Trasforma, quando è possibile, le seguenti frasi da attive in passive..  Ho affittato la casa

● Spesso in fisica i nomi delle unità di misura derivano da quelli di famosi scienziati. ● Più di 5 milioni di anni fa le acque del nostro