Automatas

TRABAJO COLABORATIVO No. 1

Obtener el lenguaje reconocido por el siguiente AFD:

A = ({q0, q1, q2, q3, q4}, {a, b, c}, f, q0, {q2})

f(q0, a) = q1 f(q0, b) = q4 f(q0, c) = q4
f(q1, a) = q4f(q1, b) = q1 f(q1, c) = q2
f(q2, a) = q4 f(q2, b) = q4 f(q2, c) = q2
f(q3, a) = q4 f(q3, b) = q3 f(q3, c) = q2
f(q4, a) = q4 f(q4, b) = q4 f(q4, c) = q4
Tabla de transición

F A B C
- q0q1 q4 q4
q1 q4 q1 q2

q2 q4 q4 q2
q3 q4 q3 q2
q4 q4 q4 q4


Entrada  q0 Estado inicial
El lenguaje reconocido por el AFD es:

ba*b*c*
ca*b*c*
ab*aa*b*c*
ab*cc*aa*b*c*ab*cc*ba*b*c*




2. Determinar el lenguaje que reconoce el siguiente AFD:



El lenguaje que reconoce el autómata AFD es:

1*2*311*2*3*
1*2*321*2*3*
1*2*331*2*3*
L (A) = { 1^(n_1 )2^(n_2 ) 1^(n_3 ) 2^(n_4 )…3/ n_1,n_2,…≥0 }

3. Dado el autómata finito siguiente:




∑= {0, 1}

G = (∑n, ∑t, P, $) = (Q, ∑, P, q0)

∑N = Q, los estados del autómata determinan lossímbolos no–terminales de la gramática.
∑T = ∑, los símbolos del autómata determinan los símbolos terminales de la gramática.
$ = q0, el estado inicial del autómata determina el símbolo inicial de lagramática

G = ({B, C, D, E}, {0, 1} P, $)

$  0B, $ 1C, B  0B, B  1B, C  0C, C  1D, D  0E, D  0, D  1E, D  1, E  0E, E  0, E 1E, E  1,

El lenguaje reconocido es: L (A)= {0, 001, 11,101, 1101, 10101, 110101, 1010101}


4. Decir cuales de las siguientes palabras son reconocidas por el siguiente AFND:


AFND: 110, 01, 100

AFND = ({0,1}, {q0, q1, q2}, q0, {q1})


f(q0,0) = ∅ f(q0, 1) = {q1, q2} f(q0, λ) = ∅
f(q1, 0) = {q0} f(q1, 1) = {q0, q1} f(q1, λ) = {q0}
f(q2, 0) = {q2} f(q2, 1) = ∅ f(q2, λ) = {q1}



Reconoce el 110 y 100 definido por:

F`={q` ε Q`/qf ε q y qf ε F}

F` (A1) = {1 (1n 0n 1n 0n) /n ≥0}

110, esta dado por:

(q0, 1) = q1 (q1, λ) = q0 (q0, 1) = q2 (q2, 0) = q2 (q2, λ) = q1 / q1  F

100 dado por:

(q0, 1) =...