C A P Per ciascuno dei seguenti linguaggi, costruire un automa riconoscitore, possibilmente deterministico. 1. Esercitazione V

LINGUAGGI FORMALI E COMPILATORI AA10/11–UNIVERSITÀ DELLA CALABRIA

DOCENTE:ING.GIANLUIGI GRECO

ESERCITATORE:ING.ENRICO MALIZIA

1

C

A

P

Per ciascuno dei seguenti linguaggi, costruire un automa riconoscitore, possibilmente deterministico.

1. L={aⁿbⁿ | n>0} U {aⁿb²ⁿ | n>0}

2. L={aⁿb^mc^k | n,m,k > 0, n=m oppure n=k}

3. L={(ab)ⁿd⁺c^md^d(ce)⁺ | n>m+p, m>0,p>0}

4. L={(wc⁺w^R)ⁿc⁺a^mb^q | n+m>q, q>=0, w {a,b}⁺} 5. L={aⁿb^mc⁺a^pb^qc^p | p{2,4}, n+p>m+q, m,n,p>0}

6. L={aⁿb^m | 0<n<=m<=2n}

7. L={(ab)ⁿ(cd)ⁿ | n>0}

8. L={aⁿb^ma^mbⁿ | n,m>0}

Esercitazione

V

LINGUAGGI FORMALI E COMPILATORI AA10/11–UNIVERSITÀ DELLA CALABRIA

DOCENTE:ING.GIANLUIGI GRECO

ESERCITATORE:ING.ENRICO MALIZIA

2

S

1. L={aⁿbⁿ | n>0} U {aⁿb²ⁿ | n>0}

2. L={aⁿb^mc^k | n,m,k > 0, n=m oppure n=k}

3. L={(ab)ⁿd⁺c^md^p(ce)⁺ | n>m+p, m>0,p>0}

LINGUAGGI FORMALI E COMPILATORI AA10/11–UNIVERSITÀ DELLA CALABRIA

DOCENTE:ING.GIANLUIGI GRECO

ESERCITATORE:ING.ENRICO MALIZIA

3 4. L={(wc⁺w^R)ⁿc⁺a^mb^q | n+m>q, q>=0, w {a,b}⁺}

5. L={aⁿb^mc⁺a^pb^qc^p | p{2,4}, n+p>m+q, m,n,p>0}

LINGUAGGI FORMALI E COMPILATORI AA10/11–UNIVERSITÀ DELLA CALABRIA

DOCENTE:ING.GIANLUIGI GRECO

ESERCITATORE:ING.ENRICO MALIZIA

4 6. L={aⁿb^m | 0<n<=m<=2n}

7. L={(ab)ⁿ(cd)ⁿ | n>0}

8. L={aⁿb^ma^mbⁿ | n,m>0}