Trabajo Práctico nº 2 Lenguajes, Expresiones y Gramáticas Regulares

Lenguajes Formales y Autómatas

Trabajo Práctico nº 2

Lenguajes, Expresiones y Gramáticas Regulares

Ejercicio 1.

Demostrá que los siguientes lenguajes son regulares utilizando la definición

1. L={ 02i , i >= 1} con Σ = {0 , 1}

L={{{0}.{0}}+}

       CB3 CB3

          CI1

       CI del CI3

1. El conjunto de todas las cadenas pertenecientes a Σ = {0 , 1} que tienen 3 ceros consecutivos

L={{{0}U{1}}*.{{0}.{0}.{0}}.{{0}U{1}}*}

      CB3 CB3 CB3 CB3 CB3 CB3 CB3

         CI2           CI1        |         CI2

          CI3                 CI1              CI3

                   CI1                             |

                        CI1

1. El lenguaje formado por los números enteros no negativos múltiplos de 3 (considerar Σ = {0 ,1, ..... , 9} )
2. L = {x / la longitud de x es impar}, con Σ = {a , b}

L={{{{a}.{a}}U{{a}.{b}}U{{b}.{b}}U{{b}.{a}}}*.{{a}U{b}}}

            CB3 CB3  CB3 CB3 CB3 CB3 CB3 CB3 CB3 CB3

                 CI1          CI1          CI1          CI1          CI2

                        CI2                         CI2                      |

                                           CI2                                |

                                           CI3                               |

                                                              CI1

Ejercicio 2.

Para cada uno de los siguientes lenguajes definidos sobre el alfabeto A = {a, b, c, d, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, demostrá que son regulares

1. L1 = { a2k b3n / k ≥ 1, n ≥ 0 }

L1={{{a}.{a}}+.{{b}.{b}.{b}}*}

      CB3.CB3+ . CB3.CB3.CB3*

          CI1+      .      CI1    .  /*

           CI3bis  .            CI1*

                  \   .           CI3

                      CI1 

1. L2 = { d2k+1  / k  ≥ 0 } ∪ { dk an  / k ≥ 0, n > 0 }

L2={{d}*.{a}+}

      CB3* .CB3+

        CI3 . CI3bis

            CI1

1. L3 = { (ab)n c (ba)2m+1 / n ≥ 1, m ≥ 0 }

L3={{{a}.{b}}+.c.{{b}.{a}}*.{{b}.{a}}}

    CB3.CB3+ .CB3. CB3.CB3* .CB3.CB3

        CI1+      . |  .        CI1*   .  CI1

        CI3bis   . | .        CI3       . /

               CI1       .            CI1

                          CI1

1. L4 = { x / x ∈ { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }*  y x es un número par}

L4={{{0}.{1}.{2}.{3}.{4}.{5}.{6}.{7}.{8}.{9}}*.{{0}.{2}.{4}.{6}.{8}}+}

  CB3.CB3.CB3.CB3.CB3.CB3.CB3.CB3.CB3.CB3* . CB3.CB3.CB3.CB3.CB3+

      CI1     .    CI1     .    CI1     .     CI1    .    CI1  *    .      CI1    .     CI1    .  /+

            CI1               .          CI1               .       /  *     .            CI1            ./+

                              CI1                           .     /*       .                      CI1+

                                            CI1*                      .                 CI3bis

                                                   CI3               .               /

                                                                   CI1

1. L5 = L1*

L5=L1*

      Ya demostrado*

       CB3

1. L6 = L3R

Ejercicio 3.

Escribí expresiones regulares que definan los siguientes lenguajes:

1. Códigos postales. (Por ej.: 1234, 8366, etc., pero no 422 o 0027).

ER= (1/2/3/4/5/6/7/8/9).(1/2/3/4/5/6/7/8/9).(1/2/3/4/5/6/7/8/9/0).(1/2/3/4/5/6/7/8/9/0)

1. Comentarios acotados por /* y */.    Σ = {letras, *, /}

ER= (/.*)/(a/b/c/d/e/f/g/h/i/j/k/l/m/n/ñ/o/p/q/r/s/t/u/v/w/x/y/z)*/(*./)

1. Identificadores de cualquier longitud que comiencen con una letra y contengan letras, dígitos o guiones. No pueden terminar con guión.

ER= (a/b/…/y/z).(a/b/…/y/z/A/B/…/Y/Z/0/1/…/8/9/-/_)*.(a/…/9)

1. Idem al anterior y que además no tengan dos guiones seguidos.

ER= (a/b/…/y/z).((a/b/…/y/z/A/B/…/Y/Z/0/1/…/8/9)+(-/_)*)*.(a/…/9)

1. L = { x /   x = ai bj  ∨ x = (cd)2n +1 ; i ≥ 0;   j,n ≥ 1}

ER= (a*.b+)/((cdcd)+(cd))

1. L = { xy /   x = a2p+1 ∧  (y = ci dj  ∨   y = an bm ) ;  p ≥ 1;   i,j ≥ 0; n,m ≥ 1}

ER= (a.(aa)+).((c*.d*)/(a+.b+))

...