MyQuestionIcon

1

You visited us 1 times! Enjoying our articles? Unlock Full Access!

Consider the ...

Question

Consider the transition diagram of a PDA given below with input alphabet $\sum = {a, b}$ and stack alphabet $Γ = {X, Z}, Z$ is the initial stack symbol.
Let L denote the language accepted by the PDA.

Which one of the following is TRUE?

Open in App

Solution

The first state accepts only a's
The third state accepts ${a^{n} b^{n} | n \geq 0}$
So, $L = {a^{n} | n \geq 0} \cup {a^{n} b^{n} | n \geq 0}$
It is a DCFL.

Suggest Corrections

thumbs-up

0

Similar questions

Q. Let P be a non-deterministic push-down automation (NPDA) with exactly one state, q, and exactly one symbol, Z, in its stack alphabet. State q is both the starting as well as the accepting state of the PDA. The stack is initialized with one Z before the start of the operation of the PDA. Let the input alphabet of the PDA be Σ.
Let L(P) be the language accepted by the PDA by reading a string and reaching its accepting state. Let N(P) be the language accepted by the PDA by reading a string and emptying its stack. Which of the following statements is TRUE?

Q. Consider the pushdown automation (PDA) below which runs over the input alphabet(a,b,c). It has the stack alphabet
{

z_{0}, x

z_{0}

is the bottom-of stack marker. The set of states of the PDA is {s,t,u,f} where s is the start state and f is the final state. The PDA accepts by final state.The transitions of the PDA given below are depicted in a standard manner. For example, the transition(s,b,X)

\to

Z_{0}

) means that if the PDA is in state s and the symbol on the top of the stack is X. then it can read b from the input and move to state t after popping the top of stack and pushing the symbols

Z_{0}

and X (in that order) on the stack.
(s,a,

Z_{0}) \to (s, X X Z_{0}

(s, ϵ, Z_{0}) \to (f, ϵ

\to (s, X X X

\to (t, ϵ

\to (t, ϵ

\to (u, ϵ

\to (u, ϵ

Z_{0}

\to (f, ϵ

)
The language accepted by the PDA is

Q. Consider the pushdown automation (PDA) below which runs over the input alphabet (a, b, c). It has the stack alpabet

{Z_{o}, X}

Z_{o}

is the bottom-of-stack marker. The set of states of the PDA is (s, t, u, f) where s is the start state and f is the final state. The transitions of the PDA given below are depicted in a standard manner. For example, the transition (s, b, X)

\to

(t, X Z_{o})

means that if the PDA is in states and the symbol on the top of the stack is X, then it can read b from the input and move to state t after popping the top of stack and pushing the symbols

Z_{o}

and X (in that order) on the stack.

(s, \in, Z_{o} \to (f, \in)

(s, a, Z_{o}) \to (S, X X Z_{o})

(s, a, X) \to (S, X X X)

(s, b, X) \to (t, \in)

(t, b, x) \to (t, \in)

(t, c, x) \to (u, \in)

(u, c, x) \to (u, \in)

(u, \in, Z_{o}) \to (f, \in

)
The language accepted by the PDA is

Q. Consider the following Turing Machine M over the alphabet {a, b} and tape alphabet

{a, b, □}

The language accepted by the above M is

C o n s i d e r t h e f o l l o w i n g N F A M, o v e r t h e a l p h a b e t a . L e t L M b e t h e l a n g u a g e a c c e p t e d b y t h e N F A M . L e t M d e n o t e t h e m a c h i n e o b t a i n e d b y t h e f i n a l a n d n o n f i n a l s t a t e s r e s p e c t i v e l y . T h e n w h i c h o f t h e f o l l o w i n g s t a t e m e n t s i s t r u e a b o u t L M a n d L M ?

View More

Join BYJU'S Learning Program

similar_icon

Related Videos

lock

Angle Bisector

Watch in App

Join BYJU'S Learning Program

CrossIcon