automatas afnd

Araceli
 Sanchis
 de
 Miguel
 
Agapito
 Ledezma
 Espino
 
José
 A.
 Iglesias
 Mar
 0}.
 
0
 

0
 

p

q
1
 

r
0,1
 

1
 
AFD1
 

A.
 Sanchis,
 A.
 Ledezma,
 J.A.
 Iglesias,
 B.
 García,
 J.
 M.Alonso
 

AFD.
 Conceptos
 Básicos
 

17
 

En
 el
 AFD1
 
•  Cuál
 es L(AFD1)
 =
 {0n
 /
 n
 >
 0}.
 
 Comprobación
 
0
 

0
 

p

q
1
 

r

1
 

Desde
 p,
 con
 el
 número
 de
 
0’s
 que
 sea,
 pero
 siempre
 al
 
menos
 uno,
 se
 llega
 al
 
estado
 final
 

A.
 Sanchis,
 A.
 Ledezma,
 J.A.
 Iglesias,
 B.
 García,
 J. M.Alonso
 

AFD.
 Conceptos
 Básicos
 

0,1
 
18
 

En
 el
 AFD1
 
•  Y
 si
 se
 hace
 F
 =
 {r},
 
 
 
L(AFD1)
 =
 {0n1x
 
 /
 n
 ≥
 0,
 x
 ∈
 Σ
 *}.
 
 

 

0
 

0
 

p

q
r

1
 
0,1
 

1
 
AFD1
 

A.
 Sanchis,
 A.
 Ledezma,
 J.A.
 Iglesias, B.
 García,
 J.
 M.Alonso
 

AFD.
 Conceptos
 Básicos
 

19
 

En
 el
 AFD1,
 


 
 

•  comprobar
 que
 si
 se
 hace
 F
 =
 {r},
 
 L(AFD1)
 =
 {0n1x
 
 /
 n
 ≥
 0,
 x
 ∈
 Σ
 *}.
 
 

0
 

p

0
 

q
1
 

r

0
 

1
 

0,1
 

p

0
 

q
1 

r

1
 

0,1
 

Desde
  p,
  con
  un
  “0”
  llego
  al
  estado
  q
  y
  desde
  allí
  se
 
pueden
 aceptar
 tantos
 0s
 como
 sean.
 
 
Luego
  con
  un
  1
  salto
  al
  estado
  final
  y
  allí
  puedo
 
terminar
 o
 reconocer
 cualquier
 cadena
 de
 0s
 y 1s.
 
 
 


 
 
 
 
 
 
 
 
 
 
 Expresión
 regular:
 LA=
 0+1
 (0+1)*
 

Expresión
 regular:
 LB=
 1(0+1)*
 

A.
 Sanchis,
 A.
 Ledezma,
 J.A.
 Iglesias,
 B.
 García,
 J.
 M.Alonso
 

AFD.
 Conceptos
 Básicos
 

20
 

En
 el
 AFD1,
 


 
 

• comprobar
 que
 si
 se
 hace
 F
 =
 {r},
 
 L(AFD1)
 =
 {0n1x
 
 /
 n
 ≥
 0,
 x
 ∈
 Σ
 *}.
 
 

0
 

0
 

p

q
1
 

r

LB=
 1(0+1)*
 

1
 

LA=
 0+1
 (0+1)*
 

0,1
 
Expresión
 regular
 LA
 U
 LB
 =
 0*1(0+1)*
 

A.
 Sanchis,
 A.
 Ledezma,
 J.A. Iglesias,
 B.
 García,
 J.
 M.Alonso
 

AFD.
 Conceptos
 Básicos
 

21
 

Estados
 accesibles
 y
 Autómatas
 conexos:
 
• 

Sea
 un
 AFD
 =
 (Σ,
 Q,
 f,
 q0,
 F),
 
 el
 estado
 p
 ∈
 Q
 es
 ACCESIBLE
 desde
 q
 ∈
 Q
 
si
 ∃
 x
 ∈
 Σ*
 
 f’(q,x)
 =
 p.
 En otro
 caso
 se
 dice
 que
 INACCESIBLE.
 
Todo
 estado
 es
 accesible
 desde
 sí
 mismo
 pues
 f’(p,λ)
 =
 p
 

Teoremas:
 
§  teorema
 3.2.2,
 libro
 1
 de
 la
 bibliograya.
 

 
 Sea
 un
 AFD,
 ⏐Q⏐=
 n,
 ∀
 p,
 q
 ∈
 Q
 
 
 p
 es
 accesible
 desde
 q
 
 sii
 ∃
 x∈Σ*,
 ⏐x⏐<
 n
 
 /
 f’(p,x)
 =
 q
 
§  teorema
 3.2.3,
 libro
 1
 de
 la
 bibliograya
 
Sea
 un
 AFD,
 ⏐Q⏐=
 n,
 entonces
 LAFD
 ≠φ
 
 sii
 el
 AFD
 acepta
 al
 menos
 
una
 palabra
 x∈Σ*,
 ⏐x⏐<
 n
 
 
Nota:
 sii=
 “si
 y
 solo
 si”
 

A....