Pics

Ejercicios sobre aut´matas finitos y otras m´quinas deterministas o a
IG29: Compiladores e int´rpretes e Cuarta sesi´n de teor´ o ıa

Bloque 1: Ejercicios de examen
Ejercicio 1 Valor: 2,50 puntosSea L el lenguaje de todas las cadenas formadas por cero o m´s letras min´sculas y que no tienen tres bes seguidas en su a u interior. As´ por ejemplo, las siguientes cadenas pertenecer´ a L:xyz, bb, bebebe, baobab, λ. Pero no estas otras: Gato, ı, ıan abbbba, xxxbbb, salu2... Consideremos tambi´n dos subconjuntos disjuntos del lenguaje L: e L1 , el conjunto de las cadenas de L que acabanen be. L2 , el conjunto de las cadenas de L que acaban en una letra distinta de be. Obs´rvese que λ, aunque es una cadena de L, no pertenece a ninguno de los subconjuntos que acabamos de definir. e A.Representa gr´ficamente un aut´mata finito determinista que reconozca el lenguaje L. No olvides los convenios habituales a o para marcar estados como iniciales (flecha entrante) o finales (doble c´ırculo). B. Construye una m´quina discriminadora determinista que omita letras may´sculas y que, ante cadenas no vac´ de L, emita a u ıas la categor´ FinBe o la categor´ FinNoBe seg´n el ultimo car´cter dela cadena sea o no una be; es decir, la categor´ ıa ıa u ´ a ıa FinBe se corresponder´ con el lenguaje L1 y FinNoBe se corresponder´ con L2 . Aparte de marcar adecuadamente el a a estado inicial dela m´quina y sus finales, no olvides indicar la acci´n asociada a cada uno de estos ultimos, seg´n el a o ´ u convenio habitual con flechas punteadas. C. Determina cu´l ser´ la secuencia de componentesl´xicos emitidos ante la siguiente cadena de entrada: a ıa e xyzbbbebebebaobabGatoabbbbaxxxbbbsalu2 ıa, e a Para cada componente emitido debes indicar, junto con el nombre de su categor´ su lexemaentre par´ntesis. Adem´s, si se produce alg´n error l´xico, debes indicar en cada caso cu´l es el car´cter causante del error. u e a a

Ejercicio 2

Valor: 1,25 puntos

Considera la siguiente...