GATE CSE
Theory of Computation
Push Down Automata and Context Free Language
Previous Years Questions

## Marks 1

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...
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... Consider the language L = {{a^n}|n \ge 0$$}$$ \cup $${$${a^n}{b^n}|n \ge 0$$} and the following statements. I. L is deterministic context-free... Which of the following languages is generated by the given grammar?$$S \to aS|bS|\varepsilon $$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... Which one of the following is FALSE?$$S \to aSa\,\left| {\,bSb\,\left| {\,a\,\left| {\,b} \right.} \right.} \right.$$The language generated by the above grammar over the alphabet$$\le... 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 \... 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... The language accepted by a pushdown Automation in which the stack is limited to$$10$$items is best described as Which of the following statement is true? Context free languages are closed under: 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... Consider the grammar with the following productions.$$S \to a\,\alpha \,\,b\left| {\,\,b\,\alpha } \right.\,c\,\left| {aB} \right.S \to \alpha S... State whether the following statement is TRUE / FALSE. A minimal $$DFA$$ that is equivalent to an $$NFDA$$ with $$n$$ modes has always 2n states... State whether the following statement is TRUE / FALSE. Regularity is preserved under the operation of string reversal. State whether the following statement is TRUE / FALSE. All subjects of regular sets are regular. State whether the following statement is TRUE / FALSE. The intersection of two $$CFL's$$ is also $$CFL.$$ State whether the following statement is TRUE / FALSE. A is recursive if both a and its complement are accepted by Turing Machine M accepts. State whether the following statement is TRUE / FALSE. The problem is to whether a Turing Machine M accepts input $$w$$ is un-decidable. ## Marks 2 Suppose that L1 is a regular and L2 is a context-free language, Which one of the following languages is NOT necessarily context-free?... Consider the following context-free grammar where the set of terminals is {a, b, c, d, f}. S → d a T | R f T → a S | b a T | ϵ R&nbs... In a pushdown automaton P = (Q, ∑, Γ, δ, q0, F), a transition of the form, where p, q ∈ Q, a ∈ Σ ∪ {ϵ}, and X,... Let $$\left\langle M \right\rangle$$ denote an encoding of an automation M. Suppose that ∑ = {0, 1}. Which of the following languages ... 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?... Consider the following languages: $$\,\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\,$$ $$\left\{ {{a^m}{b^n}{c^p}{d^q}} \right.|m + p = n + q,$$ where $$\left... Consider the following context-free grammars:$$\eqalign{ & {G_1}:\,\,\,\,\,S \to aS|B,\,\,B \to b|bB \cr & {G_2}:\,\,\,\,\,S \to aA|bB... 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}... Consider the following languages over the alphabet\sum { = \left\{ {0,\,1,\,c} \right\}:} \eqalign{ & {L_1} = \left\{ {{0^n}\,{1^n}\,\l... Consider the $$DFA$$ $$A$$ given below. Which of the following are FALSE? $$1.$$ Complement of $$L(A)$$ is context - free. $$2.$$ $$L(A)$$ $$= \le... 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.}...
A deterministic finite automation $$(DFA)$$ $$D$$ with alphabet $$\sum { = \left\{ {a,b} \right\}}$$ is given below Which of the following finite s...
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 ... Which of the following statement is false? Which of the following statements are true?1.$$Every left-recursive grammar can be converted to a right-recursive grammar and vice-versa$$2.$$... Match the following List-$${\rm I}$$with List -$${\rm II}$$List-$${\rm I}E)$$Checking that identifiers are declared before their$$F)$$Numbe... The language$$L = \left\{ {{0^i}{{21}^i}\,|\,i \ge 0} \right\}$$over the alphabet$$\left\{ {0,1,2} \right\}$$is 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... 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... 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.\$...
Let $${N_f}$$ and $${N_p}$$ denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, re...
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 &... Consider the language :$${L_1}\, = \left\{ {w\,{w^R}\,\left| {w \in \left\{ {0,1} \right\}{}^ * } \right.} \right\}{L_2}\, = \left\{ {w\, \ne {...
Consider the following grammar $$G:$$ \eqalign{ & S \to bS\,\left| {\,aA\,\left| {\,b} \right.} \right. \cr & A \to bA\,\left| {\,aB}... The language\left\{ {{a^m}{b^n}{c^{m + n}}\left| {m,n \ge } \right.} \right\}$$is Let$$M = \left( {K,\,\sum {,\,F,\,\Delta ,\,s,\,F} } \right)$$be a pushdown automation. Where$$K = \left\{ {s,\,f} \right\},\,F = \left\{ f \right\...
Consider the following decision problems: $${P_1}$$ Does a given finite state machine accept a given string $${P_2}$$ Does a given context free gramma...
If $${L_1}$$ is a context free language and $${L_2}$$ is a regular which of the following is/are false?
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 ...
Which of the following statements is false?
Which of the following languages over $$\left\{ {a,b,c} \right\}$$ is accepted by Deterministic push down automata?
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. ...
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...
Which of the following features cannot be captured by context-free grammars?
Context-free languages are
Context free languages and regular languages are both closed under the operation(s) of :
A context-free grammar is ambiguous if:
FORTRAN is:
EXAM MAP
Joint Entrance Examination