Construcción de Autómatas Finitos

Contenido de esta página:

  • Introducción

  • Problemas: construcción de autómatas finitos


Introducción

En esta sección vamos a ver cómo construir autómatas finitos (deterministas y no deterministas y con y sin pila) a partir de expresiones regulares o de la propia definición del lenguaje.

Recordamos al lector que las expresiones regulares son una forma de representar un lenguaje (regular). Veamos algunos ejemplos:

  • 0(11)*

    El lenguaje de esta expresión regular lo conforman las palabras que empiezan por 0 seguidas de un número par de 1's (el asterisco significa que la subcadena a la que enierra puede repetirse tantas veces como se desee).

    La palabra w = 0 también es una palabra de dicho lenguaje y corresponde al caso en que la subcadena 11 se repite 0 veces.

  • (1+0)1*

    El lenguaje está formado por las palabras que empiezan por 0 o por 1 (el signo + representa la unión, es decir, o uno u otro) y que están seguidas (o no) por 1's.

  • (000)*

    Representa el lenguaje formado por las cadenas con un número múltiplo de 3 de ceros.

    La palabra vacía, ε, también forma parte de este lenguaje.

    También podemos escribir este lenguaje como

    $$ L = \{ 0^{3n} : n \geq 0,\ n \in \mathbb{N} \}$$

  • L = { 1 n 0 m : n, m ≥ 0 naturales}

    Este lenguaje también puede expresarse mediante la expresión regular 0*1*. Sin embargo, si exigimos que n = m ya no es posible expresarlo mediante una expresión regular ya que dicho lenguaje no es regular. Es un lenguaje libre del contexto.


Páginas relacionadas:

Problemas resueltos

PROBLEMA 1

Dado el alfabeto

$$ \Sigma = \{ 0,1 \}$$

construir un Autómata Finito Determinista de 4 estados como máximo, que acepte el lenguaje representado por la siguiente expresión regular

$$((01 + 10)(11)^* 0)^*(01+10)(11)^*$$

Ver solución


PROBLEMA 2

Dado el alfabeto Σ = { a, b, c }, definir un Autómata Finito Determinista para el lenguaje formado por las cadenas x tales que nα (x) es par y no existe ninguna subcadena bc en x.

nα (x) representa el número de a's en la cadena x. Consideramos que el número 0 es un número par.

Ver solución


PROBLEMA 3

Dado el alfabeto Σ = { 0, 1 }, construir un Autómata Finito que acepte el siguiente lenguaje:

  • Si la cadena no tiene ningún 1, entonces la cadena debe contener un número de par de 0's (consideramos al cero como par);

  • si la cadena tiene un número par de 1's (y mayor que 0 ), la cadena debe terminar con un número impar de 0's;

  • si la cadena tiene un número impar de 1's, la cadena debe terminar con un número par de 0's.

Ver solución


PROBLEMA 4

Dado el alfabeto Σ = { 0, 1 }, considerar los siguientes lenguajes:

$$ L_1 = \{ (01)^n\ | n \geq 0 \} $$

$$ L_2 = \{ (10)^n\ | n\geq 0 \} $$

$$ L_2 = L_3 = L_1 \cup L_2 $$

Ver solución


PROBLEMA 5

Dado el alfabeto Σ = { 0, 1 }$, construir el Autómata Finito Determinista equivalente a la siguiente expresión:

$$ (((0 + 10)(10)^*(11 + 0)) + 11)(0 + 1)^*$$

Ver solución


PROBLEMA 6

Dado el alfabeto Σ = { a, b, c }, construir un autómata a pila que reconozca el siguiente lenguaje:

$$ L = \{ a^i b^j c^k a^i\ | \ i,j>0;\ k=j \}$$

Ver solución


PROBLEMA 7

Dado el alfabeto Σ = { a, b }, construir un autómata a pila que reconozca el lenguaje:

$$ L = \{ w \ | w\in \{a,b \}^*, n_a (w) \geq n_b(w) \}$$

siendo

$$n_a (w)$$

el número de a's en w y n b (w) el número de b's.

Ver solución


Inicio


Creative Commons License
Matesfacil.com by J. Llopis is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.