NEW
New Website Launch
Experience the best way to solve previous year questions with mock tests (very detailed analysis), bookmark your favourite questions, practice etc...
VISIT NOW

GATE CSE

Push Down Automata and Context Free Language

Theory of Computation

Previous Years Questions

Marks 1

More
Consider the following languages: $$\eqalign{ & {L_1} = \{ ww|w \in \{ a,b\} *\} \cr & {L_2} = \{ {a^n}{b^n}{c^m}...
GATE CSE 2022
Consider the following languages: L1 = {an wan | w $$\in$$ {a, b}*} L2 = {wxwR | w, x $$\in$$ {a, b}*, | w | , | x | > 0...
GATE CSE 2022
Consider the language L = { $${a^n}|n \ge 0$$ } $$ \cup $$ { $${a^n}{b^n}|n \ge 0$$ } and the following statements. I. L...
GATE CSE 2020
Which of the following languages is generated by the given grammar? $$$S \to aS|bS|\varepsilon $$$
GATE CSE 2016 Set 1
The lexical analysis for a modern computer language such as java needs the power of which one of the following machine m...
GATE CSE 2011
$$S \to aSa\,\left| {\,bSb\,\left| {\,a\,\left| {\,b} \right.} \right.} \right.$$ The language generated by the above g...
GATE CSE 2009
Which one of the following is FALSE?
GATE CSE 2009
Let $${L_1} = \left\{ {{0^{n + m}}{1^n}{0^m}\left| {n,m \ge 0} \right.} \right\},$$ $$\,\,\,{L_2} = \left\{ {{0^{n + m}...
GATE CSE 2006
Which of the following grammar rules violate the requirements of an operator grammar ? $$P,$$ $$Q, R$$ are non-terminals...
GATE CSE 2004
The language accepted by a pushdown Automation in which the stack is limited to $$10$$ items is best described as
GATE CSE 2002
Which of the following statement is true?
GATE CSE 2001
Context free languages are closed under:
GATE CSE 1999
Let $${L_D}$$ be the set of all languages accepted by a $$PDA$$ by final state and $${L_E}$$ the set of all languages ac...
GATE CSE 1999
Consider the grammar with the following productions. $$S \to a\,\alpha \,\,b\left| {\,\,b\,\alpha } \right.\,c\,\left| {...
GATE CSE 1995
State whether the following statement is TRUE / FALSE. The problem is to whether a Turing Machine M accepts input $$w$$ ...
GATE CSE 1990
State whether the following statement is TRUE / FALSE. The intersection of two $$CFL's$$ is also $$CFL.$$
GATE CSE 1990
State whether the following statement is TRUE / FALSE. A is recursive if both a and its complement are accepted by Turin...
GATE CSE 1990
State whether the following statement is TRUE / FALSE. Regularity is preserved under the operation of string reversal....
GATE CSE 1990
State whether the following statement is TRUE / FALSE. A minimal $$DFA$$ that is equivalent to an $$NFDA$$ with $$n$$ m...
GATE CSE 1990
State whether the following statement is TRUE / FALSE. All subjects of regular sets are regular.
GATE CSE 1990

Marks 2

More
Let $$\left\langle M \right\rangle $$ denote an encoding of an automation M. Suppose that ∑ = {0, 1}. Whi...
GATE CSE 2021 Set 1
In a pushdown automaton P = (Q, ∑, Γ, δ, q0, F), a transition of the form, where p, q ∈ Q, a&nb...
GATE CSE 2021 Set 1
Consider the following context-free grammar where the set of terminals is {a, b, c, d, f}. S → d a T | R f T&nbsp...
GATE CSE 2021 Set 1
Suppose that L1 is a regular and L2 is a context-free language, Which one of the following languages is NOT necessarily ...
GATE CSE 2021 Set 1
Consider the following languages. L1 = {wxyx | w, x, y ∈ (0 + 1)+} L2 = {xy | x, y ∈ (a + b)*, |x| = |y|, x ≠ y} Which o...
GATE CSE 2020
Consider the following languages: $$\,\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\,$$ $$\left\{ {{a^m}{b^n}{c^p}{d^q}} \right.|...
GATE CSE 2018
Consider the following context-free grammars: $$\eqalign{ & {G_1}:\,\,\,\,\,S \to aS|B,\,\,B \to b|bB \cr &am...
GATE CSE 2016 Set 1
Which of the following languages are context-free? $$$\eqalign{ & {L_1} = \left\{ {{a^m}{b^n}{a^n}{b^m}|m,n \ge 1...
GATE CSE 2015 Set 3
Consider the following languages over the alphabet $$\sum { = \left\{ {0,\,1,\,c} \right\}:} $$ $$\eqalign{ & {L_...
GATE CSE 2014 Set 3
Consider the $$DFA$$ $$A$$ given below. Which of the following are FALSE? $$1.$$ Complement of $$L(A)$$ is context - f...
GATE CSE 2013
A deterministic finite automation $$(DFA)$$ $$D$$ with alphabet $$\sum { = \left\{ {a,b} \right\}} $$ is given below W...
GATE CSE 2011
Consider the languages $${L_1}$$, $${L_2}$$ and $${L_3}$$ are given below. $$$\eqalign{ & {L_1} = \left\{ {{0^p}{1...
GATE CSE 2011
Consider the languages $$$\eqalign{ & {L_1} = \left\{ {{0^i}{1^j}\,\left| {i \ne j} \right.} \right\},\,{L_2} = \...
GATE CSE 2010
Match the following List-$${\rm I}$$ with List - $${\rm II}$$ List-$${\rm I}$$ $$E)$$ Checking that identifiers are decl...
GATE CSE 2008
Which of the following statements are true? $$1.$$ Every left-recursive grammar can be converted to a right-recursive g...
GATE CSE 2008
Which of the following statement is false?
GATE CSE 2008
Consider the $$CFG$$ with $$\left\{ {S,A,B} \right\}$$ as the non-terminal alphabet, $$\left\{ {a,b} \right\}$$ as the t...
GATE CSE 2007
The language $$L = \left\{ {{0^i}{{21}^i}\,|\,i \ge 0} \right\}$$ over the alphabet $$\left\{ {0,1,2} \right\}$$ is
GATE CSE 2007
Consider the $$CFG$$ with $$\left\{ {S,A,B} \right\}$$ as the non-terminal alphabet, $$\left\{ {a,b} \right\}$$ as the t...
GATE CSE 2007
Consider the following statements about the context-free grammar $$G = \left\{ {S \to SS,\,S \to ab,\,S \to ba,\,S \to \...
GATE CSE 2006
Consider the language : $${L_1}\, = \left\{ {w\,{w^R}\,\left| {w \in \left\{ {0,1} \right\}{}^ * } \right.} \right\}$$ ...
GATE CSE 2005
Consider the language : $${L_1} = \left\{ {{a^n}{b^n}{c^m}\left| {n,m > 0} \right.} \right\}$$ and $${L_2} = \left\{...
GATE CSE 2005
Let $${N_f}$$ and $${N_p}$$ denote the classes of languages accepted by non-deterministic finite automata and non-determ...
GATE CSE 2005
Let $$M = \left( {K,\,\sum {,\,F,\,\Delta ,\,s,\,F} } \right)$$ be a pushdown automation. Where $$K = \left\{ {s,\,f} \r...
GATE CSE 2004
The language $$\left\{ {{a^m}{b^n}{c^{m + n}}\left| {m,n \ge } \right.} \right\}$$ is
GATE CSE 2004
Consider the following grammar $$G:$$ $$\eqalign{ & S \to bS\,\left| {\,aA\,\left| {\,b} \right.} \right. \cr ...
GATE CSE 2004
Consider the following decision problems: $${P_1}$$ Does a given finite state machine accept a given string $${P_2}$$ Do...
GATE CSE 2000
If $${L_1}$$ is a context free language and $${L_2}$$ is a regular which of the following is/are false?
GATE CSE 1999
Which of the following statements is false?
GATE CSE 1998
Let $$L$$ be the set of all binary strings whose last two symbols are the same. The number of states in the minimum sta...
GATE CSE 1998
Which of the following languages over $$\left\{ {a,b,c} \right\}$$ is accepted by Deterministic push down automata?
GATE CSE 1997
Let $$G$$ be a context free grammar where $$G = \left( {\left\{ {S,A,.B,C} \right\},\left\{ {a,b,d} \right\},P,S} \right...
GATE CSE 1996
If $${L_1}$$ and $${L_2}$$ are context free languages and $$R$$ a regular set, one of the languages below is not necessa...
GATE CSE 1996
Which of the following features cannot be captured by context-free grammars?
GATE CSE 1994
Context-free languages are
GATE CSE 1992
Context free languages and regular languages are both closed under the operation(s) of :
GATE CSE 1989
FORTRAN is:
GATE CSE 1987
A context-free grammar is ambiguous if:
GATE CSE 1987

Joint Entrance Examination

JEE Main JEE Advanced WB JEE

Graduate Aptitude Test in Engineering

GATE CSE GATE ECE GATE EE GATE ME GATE CE GATE PI GATE IN

Medical

NEET

CBSE

Class 12