En un autómata pushdown P=(Q,Σ,Γ,δ,q0,F), una transición de la forma,
donde p,q∈Q, a∈σ∪{ϵ}, X,Y,∈Γ∪{ϵ}, representa
(q,Y) ∈ δ(p,a,X)
Considere el siguiente autómata pushdown sobre el alfabeto de entrada Σ={a,b} y el alfabeto de pila Γ={#,A}.
El número de strings de longitud 100 aceptadas por el autómata pushdown anterior es ___________.
(A) 50
(B) 100
(C) 55
(D) 45
Respuesta: (A)
Explicación: Según la pregunta dada,
L = {anbm| n>m & n+m=100}
L = a51b49,…..,a99b,a100
|L| = 50
Para llegar a q3 desde q2 debe haber «A» en la parte superior de la pila, por lo tanto, n>m.
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA