Push Down Automata and Context Free Language · Theory of Computation · GATE CSE

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.

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

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

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

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

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: