Context-Free Languages

Consider the following grammar where $S$ is the start symbol, and $a$ and $b$ are terminal symbols. $$ S \rightarrow a S b S|b S| \in $$ Which of the following statements is/are true?

Let $\Sigma=\{a, b, c, d\}$ and let $L=\left\{a^i b^j c^k d^l \mid i, j, k, l \geq 0\right\}$. Which of the following constraints ensure(s) that the language $L$ is context-free?

Which of the following grammars is/are ambiguous?

Consider the following context-free grammar $G$, where $S, A$, and $B$ are the variables (nonterminals), $a$ and $b$ are the terminal symbols, $S$ is the start variable, and the rules of $G$ are described as: $$\begin{al...

Which ONE of the following languages is accepted by a deterministic pushdown automaton?

Consider the following two languages over the alphabet $\{a, b, c\}$, where $m$ and $n$ are natural numbers. $$\begin{aligned} & L_1=\left\{a^m b^m c^{m+n} \mid m, n \geq 1\right\} \\ & L_2=\left\{a^m b^n c^{m+n} \mid m,...

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 symbol S . The string w = a 30 b 30 c 30 is derivable from S . The numbe...

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)$, $n_b(w)$, $n_c(w)$ denote the number of times $a$, $b$, $c$ occur...

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-terminals, and a and b are terminal symbols. The starting non-terminal is S. Which one of t...

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} = \{ {a^m}{b^n}{c^n}|m,\,n \ge 0\} \cr} $$ Which of the following statements is/...

For a string w, we define w R to be the reverse of w. For example, if w = 01101 then w R = 10110. Which of the following languages is/are context-free?

Let L 1 be a regular language and L 2 be a context-free language. Which of the following languages is/are context-free?

Suppose that L 1 is a regular and L 2 is a context-free language, Which one of the following languages is NOT necessarily context-free?

Consider the following languages. L 1 = {wxyx | w, x, y ∈ (0 + 1) + } L 2 = {xy | x, y ∈ (a + b)*, |x| = |y|, x ≠ y} Which one of the following is TRUE?

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. II. L is context-free but not deterministic context-free. III. L is...

Which one of the following languages over $\Sigma=\{a, b\}$ is NOT context-free?

Consider the following languages: $$\,\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\,$$ $$\left\{ {{a^m}{b^n}{c^p}{d^q}} \right.|m + p = n + q,$$ where $$\left. {m,n,p,q \ge 0} \right\}$$ $$\,\,\,\,\,\,{\rm II}.\,\,\,\,\,\,\,$$ $$\...

Consider the following context-free grammars: $$\eqalign{ & {G_1}:\,\,\,\,\,S \to aS|B,\,\,B \to b|bB \cr & {G_2}:\,\,\,\,\,S \to aA|bB,\,\,A \to aA|B|\varepsilon ,\,\,B \to bB|\varepsilon \cr} $$ Which one of the follow...

Which of the following languages is generated by the given grammar? $$$S \to aS|bS|\varepsilon $$$

Language $${L_1}$$ is defined by the grammar: $$S{}_1 \to a{S_1}b|\varepsilon $$ Language $${L_2}$$ is defined by the grammar: $$S{}_2 \to ab{S_2}|\varepsilon $$ Consider the following statements: $$P:$$ $${L_1}$$ is reg...

Consider the following languages : $$$\eqalign{ & {L_1} = \left\{ {{a^n}{b^m}{c^{n + m}}:m,n \ge 1} \right\} \cr & {L_2} = \left\{ {{a^n}{b^n}{c^{2n}}:n \ge 1} \right\} \cr} $$$ Which one of the following is TRUE ?

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} = \left\{ {{a^m}{b^n}{a^m}{b^n}|m,n \ge 1} \right\} \cr & {L_3} = \left\{ {{a^m}{b^n...

Consider the following languages over the alphabet $$\sum { = \left\{ {0,\,1,\,c} \right\}:} $$ $$\eqalign{ & {L_1} = \left\{ {{0^n}\,{1^n}\,\left| {n \ge } \right.0} \right\} \cr & {L_2} = \left\{ {wc{w^r}\,\left| {w \i...

Consider the following languages $${L_1} = \left\{ {{0^p}{1^q}{0^r}\left| {p,q,r \ge 0} \right.} \right\}$$ $${L_2} = \left\{ {{0^p}{1^q}{0^r}\left| {p,q,r \ge 0,p \ne r} \right.} \right\}$$ Which one of the following st...

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.} \right\} \cr & {L_2} = \left\{ {{0^p}{1^q}\left| {p,q \in N} \right.\,\,and...

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 = j} \right.} \right\}, \cr & {L_3} = \left\{ {{0^i}{1^j}\,\left| {i = 2j + 1...

$$S \to aSa\,\left| {\,bSb\,\left| {\,a\,\left| {\,b} \right.} \right.} \right.$$ The language generated by the above grammar over the alphabet $$\left\{ {a,\,b} \right\}$$ is the set of

Which one of the following 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.$$ All ε-productions can be removed from any context-free grammar by suitab...

Match the following List-$${\rm I}$$ with List - $${\rm II}$$ List-$${\rm I}$$ $$E)$$ Checking that identifiers are declared before their $$F)$$ Number of formal parameters in the declaration of a function agrees with th...

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 { S, A, B } as the non-terminal alphabet, { a, b } as the terminal alphabet, S as the start symbol and the following set of production rules: $$\eqalign{ & S \to bA\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,...

Consider the CFG with { S, A, B } as the non-terminal alphabet, { a, b } as the terminal alphabet, S as the start symbol and the following set of production rules: $$\eqalign{ & S \to bA\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,...

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 \ge 0} \right.} \right\},$$ and $$\,\,\,\,{L_3} = \left\{ {{0^{n + m}}{1...

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.$$ $$G$$ is ambiguous $$2.$$ $$G$$ produces all strings with equal numbe...

Which one of the following grammars generates the following language? $$L = \left( {{a^i}{b^j}|i \ne j} \right)$$

In the correct grammar of the previous question, what is the length of the derivation (number of steps starring from S) to generate the string $${a^l}{b^m}$$ with $$l \ne m$$?

Let $${N_f}$$ and $${N_p}$$ denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, respectively. Let $${D_f}$$ and $${D_p}$$ denote the classes of language...

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 > 0} \right.} \right\}$$ Which of the following statement is FALSE?

Consider the language : $${L_1}\, = \left\{ {w\,{w^R}\,\left| {w \in \left\{ {0,1} \right\}{}^ * } \right.} \right\}$$ $${L_2}\, = \left\{ {w\, \ne {w^R}\,\left| {w \in \left\{ {0,1} \right\}{}^ * } \right.} \right\}$$ w...

Consider the following grammar $$G:$$ $$\eqalign{ & S \to bS\,\left| {\,aA\,\left| {\,b} \right.} \right. \cr & A \to bA\,\left| {\,aB} \right. \cr & B \to bB\,\left| {\,aS\,\left| {\,a} \right.} \right. \cr} $$ Let $${N...

The language $$\left\{ {{a^m}{b^n}{c^{m + n}}\left| {m,n \ge } \right.} \right\}$$ is

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. $$$\eqalign{ & 1)\,\,\,P \to Q\,R\,\,\,\,\,2)\,\,\,P \to Q\,s\,R \cr...

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?

Let $$L$$ denote the language generated by the grammar $$S \to 0S\left. 0 \right|00.$$ Which one of the following is true?

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 of the following is true?

If $${L_1}$$ is a context free language and $${L_2}$$ is a regular which of the following is/are false?

Context free languages are closed under:

Regarding the power of recognition of languages, which of the following statement 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. Which one?

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$$ given below $$\eqalign{ & S \to ABAC\,\,\,\,\,\,\,\,\,S \to aA{\mkern 1mu...

Consider the grammar with the following productions. $$S \to a\,\alpha \,\,b\left| {\,\,b\,\alpha } \right.\,c\,\left| {aB} \right.$$ $$S \to \alpha S\,\left| b \right.$$ $$S \to \alpha \,bb\,\left| {ab} \right.$$ $$S\al...

Which of the following definitions below generates the same language as $$L$$ Where $$L = {\left\{ x \right.^n}{y^n}\left| {n \ge \left. 1 \right\}} \right.$$ i) $$\,\,E \to xEy\left| {xy} \right.$$ ii) $$\,\,xy\left| {\...

Which of the following features cannot be captured by context-free grammars?

Which of the following conversions is not possible (algorithmically)?

If $$G$$ is a context-free grammar and $$w$$ is a string of length $$n$$ in $$L(G),$$ how long is a derivation of $$w$$ in $$G,$$ if $$G$$ is Chomsky normal form?

State whether the following statement is TRUE / FALSE. The intersection of two $$CFL's$$ is also $$CFL.$$

Context free languages and regular languages are both closed under the operation(s) of :

A context-free grammar is ambiguous if: