MyQuestionIcon

1

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

Introduction to PDA

Consider the ...

Question

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?

Open in App

Solution

If L is accepted by some DPDA then L must be deterministic context free language. The grammar that generates L will be deterministic context free grammer. Also, A DCFG is the same as are LF(0) grammer. All LR(K) grammers are unambiguous. Hence Statement-I is true. Statement-2 is true because PDA with final state has same expressive power as that of PDA with empty stack.

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. Consider the following two statements :

I. If all states of an NFA are accepting states then the language accepted by the NFA is

\sum^{*}

.

II. There exists a regular language A such that for all languages B,

A \cap B

is regular.

Which one of the following is CORRECT?

Q. 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?

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. 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?

View More

Join BYJU'S Learning Program

similar_icon

Related Videos

lock

Introduction to PDA

OTHER

Watch in App

explore_more_icon

Explore more

Introduction to PDA

Join BYJU'S Learning Program

CrossIcon