Computer Science Engineering (CSE) Exam  >  Computer Science Engineering (CSE) Tests  >  Question Bank for GATE Computer Science Engineering  >  Test: Pushdown Automata: CFL & DCFL- 2 - Computer Science Engineering (CSE) MCQ

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


Test Description

15 Questions MCQ Test Question Bank for GATE Computer Science Engineering - Test: Pushdown Automata: CFL & DCFL- 2

Test: Pushdown Automata: CFL & DCFL- 2 for Computer Science Engineering (CSE) 2024 is part of Question Bank for GATE Computer Science Engineering preparation. The Test: Pushdown Automata: CFL & DCFL- 2 questions and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus.The Test: Pushdown Automata: CFL & DCFL- 2 MCQs are made for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests for Test: Pushdown Automata: CFL & DCFL- 2 below.
Solutions of Test: Pushdown Automata: CFL & DCFL- 2 questions in English are available as part of our Question Bank for GATE Computer Science Engineering for Computer Science Engineering (CSE) & Test: Pushdown Automata: CFL & DCFL- 2 solutions in Hindi for Question Bank for GATE Computer Science Engineering course. Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Attempt Test: Pushdown Automata: CFL & DCFL- 2 | 15 questions in 45 minutes | Mock test for Computer Science Engineering (CSE) preparation | Free important questions MCQ to study Question Bank for GATE Computer Science Engineering for Computer Science Engineering (CSE) Exam | Download free PDF with solutions
Test: Pushdown Automata: CFL & DCFL- 2 - Question 1

Which of the following is false?

Detailed Solution for Test: Pushdown Automata: CFL & DCFL- 2 - Question 1

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

Test: Pushdown Automata: CFL & DCFL- 2 - Question 2

For the grammar given below, what is the equivalent CFG without useless symbols 

Detailed Solution for Test: Pushdown Automata: CFL & DCFL- 2 - Question 2

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

1 Crore+ students have signed up on EduRev. Have you? Download the App
Test: Pushdown Automata: CFL & DCFL- 2 - Question 3

For the given grammar below, what is the equivalent CFG without ∈ -productions? 

Detailed Solution for Test: Pushdown Automata: CFL & DCFL- 2 - Question 3

For the given grammar:

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

Test: Pushdown Automata: CFL & DCFL- 2 - Question 4

What is the equivalent CFL for the following CFG 

Detailed Solution for Test: Pushdown Automata: CFL & DCFL- 2 - Question 4

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 

Test: Pushdown Automata: CFL & DCFL- 2 - Question 5

For the given grammar below, what is the equivalent CFG without ∈-productions?

Detailed Solution for Test: Pushdown Automata: CFL & DCFL- 2 - Question 5

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.

Test: Pushdown Automata: CFL & DCFL- 2 - Question 6

What is the equivalent CFL for the following CFG? 

Detailed Solution for Test: Pushdown Automata: CFL & DCFL- 2 - Question 6

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

Test: Pushdown Automata: CFL & DCFL- 2 - Question 7

Which of the following statement is/are true?

Detailed Solution for Test: Pushdown Automata: CFL & DCFL- 2 - Question 7

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.

Test: Pushdown Automata: CFL & DCFL- 2 - Question 8

Which of the following is a CFL?

Detailed Solution for Test: Pushdown Automata: CFL & DCFL- 2 - Question 8

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

Test: Pushdown Automata: CFL & DCFL- 2 - Question 9

Which language does the following PDA accept   and b is given by

Detailed Solution for Test: Pushdown Automata: CFL & DCFL- 2 - Question 9


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

Test: Pushdown Automata: CFL & DCFL- 2 - Question 10

Which language does M accept if the following transition is added?

Detailed Solution for Test: Pushdown Automata: CFL & DCFL- 2 - Question 10


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

Test: Pushdown Automata: CFL & DCFL- 2 - Question 11

Consider the following set of languages:

Which of the above language is not context free?

Detailed Solution for Test: Pushdown Automata: CFL & DCFL- 2 - Question 11


In L1 n = m2 cannot be checkes in stack as m2 is a nonlinear function.
Hence it is not CFL.
L2 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
L3 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.

Test: Pushdown Automata: CFL & DCFL- 2 - Question 12

L has the following grammar:

L2 has the following grammar:
S → Sba\a
Which of the following statement is true about?

Detailed Solution for Test: Pushdown Automata: CFL & DCFL- 2 - Question 12

L1 and L2 are context free languages. We can see that L2 is in fact a regular language having regular expression a (ba)*.
L1 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 L4 = L1 . L2* is a context free.

Test: Pushdown Automata: CFL & DCFL- 2 - Question 13

Which of the following is not true?

Detailed Solution for Test: Pushdown Automata: CFL & DCFL- 2 - Question 13

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

Test: Pushdown Automata: CFL & DCFL- 2 - Question 14

The reduced grammar equivalent to the grammar, whose production rules are given below, is

S → AB | CA

B → BC | AB

A → a

C → a B | b

Detailed Solution for Test: Pushdown Automata: CFL & DCFL- 2 - Question 14

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.

Test: Pushdown Automata: CFL & DCFL- 2 - Question 15

Consider the CFG G( \/, T, P, S) with the following production:

Let CFG G' is an equivalent CFG with no useless symbols. How many minimum production will be there in G'?

Detailed Solution for Test: Pushdown Automata: CFL & DCFL- 2 - Question 15


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.

63 videos|7 docs|165 tests
Information about Test: Pushdown Automata: CFL & DCFL- 2 Page
In this test you can find the Exam questions for Test: Pushdown Automata: CFL & DCFL- 2 solved & explained in the simplest way possible. Besides giving Questions and answers for Test: Pushdown Automata: CFL & DCFL- 2, EduRev gives you an ample number of Online tests for practice

Top Courses for Computer Science Engineering (CSE)

Download as PDF

Top Courses for Computer Science Engineering (CSE)