Push Down Automata and Context Free Language · Theory of Computation · GATE CSE
Start PracticeMarks 1
GATE CSE 2021 Set 2
Let L1 be a regular language and L2 be a context-free language. Which of the following languages is/are context-free?
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 context-free?...
GATE CSE 2021 Set 1
Let $$\left\langle M \right\rangle $$ denote an encoding of an automation M. Suppose that ∑ = {0, 1}. Which of the following languages ...
GATE CSE 2016 Set 1
Which of the following languages is generated by the given grammar?
$$$S \to aS|bS|\varepsilon $$$
GATE CSE 2011
The lexical analysis for a modern computer language such as java needs the power of which one of the following machine model in a necessary and suffic...
GATE CSE 2009
$$S \to aSa\,\left| {\,bSb\,\left| {\,a\,\left| {\,b} \right.} \right.} \right.$$
The language generated by the above grammar over the alphabet $$\le...
GATE CSE 2009
Which one of the following is FALSE?
GATE CSE 2006
Let $${L_1} = \left\{ {{0^{n + m}}{1^n}{0^m}\left| {n,m \ge 0} \right.} \right\},$$
$$\,\,\,{L_2} = \left\{ {{0^{n + m}}{1^{n + m}}{0^m}\left| {n,m \...
GATE CSE 2004
Which of the following grammar rules violate the requirements of an operator grammar ? $$P,$$ $$Q, R$$ are non-terminals and $$r, s, t$$ are terminals...
GATE CSE 2002
The language accepted by a pushdown Automation in which the stack is limited to $$10$$ items is best described as
GATE CSE 2001
Which of the following statement is true?
GATE CSE 1999
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 accepted by empty stack. Which o...
GATE CSE 1995
Consider the grammar with the following productions.
$$S \to a\,\alpha \,\,b\left| {\,\,b\,\alpha } \right.\,c\,\left| {aB} \right.$$
$$S \to \alpha S...
GATE CSE 1990
State whether the following statement is TRUE / FALSE.
A minimal $$DFA$$ that is equivalent to an $$NFDA$$ with $$n$$ modes has always 2n states...
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.
All subjects of regular sets are regular.
GATE CSE 1990
State whether the following statement is TRUE / FALSE.
The problem is to whether a Turing Machine M accepts input $$w$$ is un-decidable.
GATE CSE 1990
State whether the following statement is TRUE / FALSE.
A is recursive if both a and its complement are accepted by Turing Machine M accepts.
GATE CSE 1990
State whether the following statement is TRUE / FALSE.
The intersection of two $$CFL's$$ is also $$CFL.$$
Marks 2
GATE CSE 2024 Set 2
Consider a context-free grammar $G$ with the following 3 rules. $S \rightarrow aS, \ S \rightarrow aSbS, S \rightarrow c$ Let $w \in L(G)$.Let $n_a(w...
GATE CSE 2024 Set 1
Let G = (V, Σ, S, P) be a context-free grammar in Chomsky Normal Form with Σ = { a, b, c } and V containing 10 variable symbols including the start ...
GATE CSE 2023
Consider the context-free grammar G below
$$\matrix{
S & \to & {aSb|X} \cr
X & \to & {aX|Xb|a|b,} \cr
} $$
where S and X are non-termi...
GATE CSE 2023
Consider the pushdown automation (PDA) P below, which runs on the input alphabet {a, b}, has stack alphabet {$$\bot$$, A}, and has three states {s, p,...
GATE CSE 2022
Consider the following languages:
L1 = {an wan | w $$\in$$ {a, b}*}
L2 = {wxwR | w, x $$\in$$ {a, b}*, | w | , | x | > 0}
Note that wR is the reversal...
GATE CSE 2022
Consider the following languages:
$$\eqalign{
& {L_1} = \{ ww|w \in \{ a,b\} *\} \cr
& {L_2} = \{ {a^n}{b^n}{c^m}|m,\,n \ge 0\} \cr
& {L_3...
GATE CSE 2021 Set 2
For a string w, we define wR to be the reverse of w. For example, if w = 01101 then wR = 10110.
Which of the following languages is/are con...
GATE CSE 2021 Set 1
In a pushdown automaton P = (Q, ∑, Γ, δ, q0, F), a transition of the form,
where p, q ∈ Q, a ∈ Σ ∪ {ϵ}, and X,...
GATE CSE 2020
Consider the following languages.
L1 = {wxyx | w, x, y ∈ (0 + 1)+}
L2 = {xy | x, y ∈ (a + b)*, |x| = |y|, x ≠ y}
Which one of the following is TRUE?...
GATE CSE 2019
Which one of the following languages over $\Sigma=\{a, b\}$ is NOT context-free?
GATE CSE 2018
Consider the following languages:
$$\,\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\,$$ $$\left\{ {{a^m}{b^n}{c^p}{d^q}} \right.|m + p = n + q,$$ where $$\left...
GATE CSE 2016 Set 1
Consider the following context-free grammars:
$$\eqalign{
& {G_1}:\,\,\,\,\,S \to aS|B,\,\,B \to b|bB \cr
& {G_2}:\,\,\,\,\,S \to aA|bB...
GATE CSE 2015 Set 3
Which of the following languages are context-free?
$$$\eqalign{
& {L_1} = \left\{ {{a^m}{b^n}{a^n}{b^m}|m,n \ge 1} \right\} \cr
& {L_2}...
GATE CSE 2014 Set 3
Consider the following languages over the alphabet $$\sum { = \left\{ {0,\,1,\,c} \right\}:} $$
$$\eqalign{
& {L_1} = \left\{ {{0^n}\,{1^n}\,\l...
GATE CSE 2013
Consider the $$DFA$$ $$A$$ given below.
Which of the following are FALSE?
$$1.$$ Complement of $$L(A)$$ is context - free.
$$2.$$ $$L(A)$$ $$ = \le...
GATE CSE 2011
Consider the languages $${L_1}$$, $${L_2}$$ and $${L_3}$$ are given below.
$$$\eqalign{
& {L_1} = \left\{ {{0^p}{1^q}\left| {p,q \in N} \right.}...
GATE CSE 2010
Consider the languages
$$$\eqalign{
& {L_1} = \left\{ {{0^i}{1^j}\,\left| {i \ne j} \right.} \right\},\,{L_2} = \left\{ {{0^i}{1^j}\,\left| {i ...
GATE CSE 2008
Match the following List-$${\rm I}$$ with List - $${\rm II}$$
List-$${\rm I}$$
$$E)$$ Checking that identifiers are declared before their
$$F)$$ Numbe...
GATE CSE 2008
Which of the following statement is false?
GATE CSE 2008
Which of the following statements are true?
$$1.$$ Every left-recursive grammar can be converted to a right-recursive grammar and vice-versa
$$2.$$ ...
GATE CSE 2007
Consider the $$CFG$$ with $$\left\{ {S,A,B} \right\}$$ as the non-terminal alphabet, $$\left\{ {a,b} \right\}$$ as the terminal alphabet, $$S$$ as the...
GATE CSE 2007
Consider the $$CFG$$ with $$\left\{ {S,A,B} \right\}$$ as the non-terminal alphabet, $$\left\{ {a,b} \right\}$$ as the terminal alphabet, $$S$$ as the...
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 2006
Consider the following statements about the context-free grammar
$$G = \left\{ {S \to SS,\,S \to ab,\,S \to ba,\,S \to \varepsilon } \right\}$$
$$1.$...
GATE CSE 2005
Let $${N_f}$$ and $${N_p}$$ denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, re...
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\{ {{a^n}{b^m}{c^m}\left| {n,m &...
GATE CSE 2005
Consider the language :
$${L_1}\, = \left\{ {w\,{w^R}\,\left| {w \in \left\{ {0,1} \right\}{}^ * } \right.} \right\}$$
$${L_2}\, = \left\{ {w\, \ne {...
GATE CSE 2004
Let $$M = \left( {K,\,\sum {,\,F,\,\Delta ,\,s,\,F} } \right)$$ be a pushdown automation. Where $$K = \left\{ {s,\,f} \right\},\,F = \left\{ f \right\...
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
& A \to bA\,\left| {\,aB}...
GATE CSE 1999
If $${L_1}$$ is a context free language and $${L_2}$$ is a regular which of the following is/are 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 state deterministic finite-state ...
GATE CSE 1998
Which of the following statements is false?
GATE CSE 1997
Which of the following languages over $$\left\{ {a,b,c} \right\}$$ is accepted by Deterministic push down automata?
GATE CSE 1996
Let $$G$$ be a context free grammar where $$G = \left( {\left\{ {S,A,.B,C} \right\},\left\{ {a,b,d} \right\},P,S} \right)$$ with productions $$P$$ giv...
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 necessarily a context free language. ...
GATE CSE 1994
Which of the following features cannot be captured by context-free grammars?
GATE CSE 1992
Context-free languages are
GATE CSE 1989
Context free languages and regular languages are both closed under the operation(s) of :
GATE CSE 1987
FORTRAN is:
GATE CSE 1987
A context-free grammar is ambiguous if: