Test: Pushdown Automata: CFL & DCFL- 2 - Computer Science Engineering (CSE) MCQ

If a language  both recursively enumerable, then both L and are recursive.

Since in grammar  is useless and so is A. Hence  is useless. Therefore the equivalent CFG is  S → a.

For the given grammar:

Only A is nullable. Hence replacing and adding at each and every place with A with ∈ we have 

The given CFG 
always produce equal number of 0'S followed by equal number of 1’s. It also contains the ∈. Hence the equivalent CFL is nothing but 

Since the CFG

So L(G), itself contain the ‘∈’ and it is not possible from a CFG to remove ‘∈ ’ production if ‘∈’ is part of the language.

The given CFG: S → aS|aSdS|∈
denotes each prefix of x has atleast as many a’s as b’s.

Concept:

Option 1: Pushdown automata = Finite automata + 0 stack

False, Pushdown Automata is a finite automaton with extra memory called stack which helps Pushdown automata to recognize Context-Free Languages.

Pushdown automata = Finite automata + stack (More than one stack)

Option 2: Pushdown automata = Finite automata + 1 stack

True, Pushdown Automata is a finite automaton with extra memory called stack which helps Pushdown automata to recognize Context-Free Languages.

Pushdown automata = Finite automata + stack (More than one stack)

Option 3: Deterministic pushdown automata is a subset of nondeterministic pushdown automata.

True, Pushdown automata with deterministic behavior are a subset of those with nondeterministic behavior. NPDA is more powerful than DPDA, it can support more languages than DPDA can, although not all languages can be supported by both groups.

Option 4:Non deterministic Pushdown Automata and Deterministic Pushdown Automata are equivalent in power.

False, There is no power equivalence between NPDAs (Non-Deterministic Pushdown Automata) and DPDAs (Deterministic Pushdown Automata). The NPDA is more effective than the DPDA, hence it exists for every language for which a DPDA exists. However, certain languages are accepted by the NPDA but not by the DPDA.

i.e DPDA < NPDA

Hence the correct answer is option D. Both Staement 2 and 3 correct.

 and we cannot determine the middle of the ww^R i.e. we cannot determine the end of ' w" and start of w^R. In all other options, there are more than one comparison.

So, strain at least contain 011, push 0, skip 1^st 1 then POP 0 for second 1, the accept by ∈, z₀, t transition.

Since ∈ can also be accepted, 0ⁿ push then skip 1^st 1, then pop all 0 for 1ⁿ and accept by transition

In L₁ n = m² cannot be checkes in stack as m² is a nonlinear function.
Hence it is not CFL.
L₂ requires 2 comparisons on number as itself 
⇒ Number of a’s = number of b’s and number of c’s. This cannot be done by single stack
L₃ requires 2 comparisons, but only one at a time is required.
⇒ Number of a’s = number of b’s and number of c’s = number of d/’s. This can be done in single stack.

L₁ and L₂ are context free languages. We can see that L₂ is in fact a regular language having regular expression a (ba)*.
L₁ is a language containing strings having equal number of a’s and b’s.
 is a context free language, 
∴ class of context free languages is closed under concatenation and kleene closure. There fore L₄ = L₁ . L_2^* is a context free.

• Every LL grammar must be unambiguous but every unambiguous need not be LL grammar.
• Ambiguity in language starts from CFL. So, DCFL cannot be inherently ambiguous.
• if G is an LR(K) grammar, then L{G) is a DCFL.
• Every CFL’s which are not DCFL need not be ambiguous.

S→AB |CA

B→BC |AB

A→a

C→aB | b

Here B is not derive any terminal string so remove productions contains B

S→CA

A→a

C→b 

Hence above grammar is Reduced grammar.

Here S → AB is useless because of symbol B.
Hence the production A → a is also useless. There fore we are left with only S → a.