MyQuestionIcon

1

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

Construction of Pushdown Automata Part - 3

Let LD be the...

Question

Let L_D be the set of all language accepted by a PDA by final state and L_E the set of all languages accepted by empty stack.
Which of the following is true?

A

L_{D} \subset L_{E}

No worries! We‘ve got your back. Try BYJU‘S free classes today!

B

L_{D} \supset L_{E}

No worries! We‘ve got your back. Try BYJU‘S free classes today!

C

None of the above

No worries! We‘ve got your back. Try BYJU‘S free classes today!

D

L_{D}

=

L_{E}

Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses

Open in App

Solution

The correct option is D $L_{D}$ = $L_{E}$
There are two approaches by which PDA accepts its input
(a) Acceptance by empty stack
(b) Accepting by entering final state.
Since there exist algorithm to convert PDA accepting by final state to PDA accepting by empty stack and vice-versa,the acceptance or recognition power of PDA of both approaches are same.Therefore L_D= L_E

Suggest Corrections

thumbs-up

0

Similar questions

Q. Consider the NFAM shown below.

Let the language accepted by M be L. let

L_{1}

be the language accepted by the NFA

M_{1}

, obtained by changing the accpeting state of M to a non-accepting state and by changing the non-accepting state of M to accepting states. Which of the following statements is true?

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?

L \subseteq {0, 1}^{*}

be an arbitrary regular language accepted by a minimal DFA with k states. Which one of the following languages must necessarily be accepted by a minimal DFA with k states?

Q. Let M be a finite automaton and let M' be obtained from M by interchanging the collections of accepting and non-accepting states.
Now consider the following statements:

I. If M is deterministic, then the language accepted by M' is the complement of the language accepted by M.

II. If M is Non-deterministic, then the language accepted by M' is the complement of the language accepted by M.

Which of the above is/are correct?

Q. Consider the following statements:

I. If L is the language accepted by some DPDA, then L has an unambiguous CFG.

II. PDA with acceptance by final state is equivalent to PDA with acceptance by empty stack.

Which of the above statements is correct?

View More

Join BYJU'S Learning Program

similar_icon

Related Videos

lock

Construction of Pushdown Automata Part - 3

OTHER

Watch in App

explore_more_icon

Explore more

Construction of Pushdown Automata Part - 3

Join BYJU'S Learning Program

CrossIcon