⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠
Text Elements
L={c (ba) | n > m >= 0}
n
m
p
c ; λ ; X
q
ccccbaba
ba ; X ; λ
ba ; X ; λ
r
λ ; X ; λ
-
Defina un autómata de pila determinista que reconozca el lenguaje
-
Arme un AP para reconocer la cadena “aaabbb”y explique el funcionamiento del mismo.
p
a ; λ ; X
q
b ; X ; λ
b ; X ; λ
r
λ ; Z ; Z
λ ; X ; λ
λ ; Z ; Z
- Diseñe la máquina de Turing que represente el siguiente lenguaje formado
L = {c^n a^(2n) | n>=1}
δ(Q0, λ) = (Q0, λ, D) δ(Q0, c) = (Q1, C, D)
δ(Q1, c) = (Q1, c, D) δ(Q1, a) = (Q1, a, D) δ(Q1, λ) = (Q2, λ, I)
δ(Q2, A) = (Q2, A, I) δ(Q2, a) = (Q3, A, I)
δ(Q3, a) = (Q4, A, I)
δ(Q4, c) = (Q5, c, I) δ(Q4, a) = (Q5, a, I) δ(Q4, C) = (Q4, C, D) δ(Q4, A) = (Q4, A, D) δ(Q4, λ) = (Q6, λ, S)
δ(Q5, c) = (Q5, c, I) δ(Q5, a) = (Q5, a, I) δ(Q5, C) = (Q0, C, D)
Q0
Q1
Q2
Q3
Q4
Q5
λ ; λ ; D
c ; C ; D
c ; c ; D
a ; a ; D
λ ; λ ; I
A ; A ; I
a ; A ; I
a ; A ; I
a ; a ; I
c ; c ; I
a ; a ; I
c ; c ; I
A ; A ; D
C ; C ; D
Q6
λ ; λ ; s
C ; C ; D
p
a ; λ ; X
q
b ; X ; λ
b ; X ; λ
r
λ ; Z ; Z
L={a b | n = 3}
n
n
Z
X
X
X
p
a ; λ ; X
q
b ; X ; λ
b ; X ; λ
r
λ ; Z ; Z
Z
X
X
p
a ; λ ; X
q
b ; X ; λ
b ; X ; λ
r
λ ; Z ; Z
Z
p
a ; λ ; X
q
b ; X ; λ
b ; X ; λ
r
λ ; Z ; Z
Z
M=(Q, Σ, T, s, λ, F, δ)
Q={Q0,Q1,Q2,Q3,Q4,Q5,Q5}
Σ={a,c}
T={a,c,λ}
F={Q6}