CFG

Let G1, G2 be Context Free Grammars (CFGs) and R be a regular expression. For a grammar G, let L(G) denote the language generated by G. Which ONE among the following questions is d...

Consider the following context-free grammar where the start symbol is S and the set of terminals is {a,b,c,d}. S → AaAb | BbBa A → cS | ε B → dS | ε The following is a partially-fi...

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

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

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

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

Which of the following decision problems are undecidable? $$\,\,\,\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\,\,\,\,$$ Given $$NFAs$$ $${N_1}$$ and $${N_2},$$ is $$L\left( {{N_1}} \right)...

A student wrote two context-free grammars G1 and G2 for generating a single $$C$$-like array declaration. The dimension of the array is at least one. For example, $$${\mathop{\rm i...

In the context of abstract-syntax-tree $$(AST)$$ and control-flow-graph $$(CFG),$$ which one of the following is TRUE?

Which of the following is/are undecidable? $$1.$$ $$G$$ is a $$CFG.$$ Is $$L\left( G \right) = \Phi ?$$ $$2.$$ $$G$$ is a $$CFG.$$ Is $$L\left( G \right) = \sum {{}^ * } ?$$ $$3.$$...

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

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

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

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

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

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$$?

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

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

A context-free grammar is ambiguous if: