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

Which of the following grammars is/are ambiguous?

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?

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

Let $G_1, G_2$ 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 decidable?

Consider the two lists List-I and List-II given below:

For matching of items in List-I with those in List-II, which of the following option(s) is/ are CORRECT?

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{aligned} & S \rightarrow a a B \mid A b b \\ & A \rightarrow a \mid a A \\ & B \rightarrow b \mid b B \end{aligned}$$

Which ONE of the languages $L(G)$ is accepted by $G$ ?

The intersection of two $$CFL's$$ is also $$CFL.$$

All subjects of regular sets are regular.

Regularity is preserved under the operation of string reversal.

A minimal $$DFA$$ that is equivalent to an $$NFDA$$ with $$n$$ modes has always 2ⁿ states

A is recursive if both a and its complement are accepted by Turing Machine M accepts.

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?

Consider the following context-free grammar $G$ :

$$ \begin{aligned} & S \rightarrow a b a A B A b b a \\ & A \rightarrow a a B B A b \mid b B a b a a \\ & B \rightarrow a B b \mid a b \end{aligned} $$

In the above grammar, $S$ is the start symbol, $a$ and $b$ are terminal symbols, and $A$ and $B$ are non-terminal symbols.

Let $L(G)$ be the language generated by the grammar $G$. For a string $s \in L(G)$, let $n_1(s)$ be the number of a's in $s$ and $n_2(s)$ be the number of b's in $s$.

Which of the following statements is/are true?

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, n \geq 1\right\} \end{aligned}$$

Which ONE of the following statements is CORRECT?

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 in $w$, respectively. Which of the following statements is/are TRUE?

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³⁰b³⁰c³⁰ is derivable from S. The number of steps (application of rules) in the derivation S ⟹ w is _______

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 the following statements is CORRECT?

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, q}, with s being the start state. A transition from state u to state v, labelled c/X/$$\gamma$$, where c is an input symbol or $$\in $$, X is a stack symbol, and $$\gamma$$ is a string of stack symbols, represents the fact that in state u, the PDA can read c from the input, with X on the top of its stack, pop X from the stack, push in the string $$\gamma$$ on the stack, and go to state v. In the initial configuration, the stack has only the symbol $$\bot$$ in it. The PDA accepts by empty stack.

Which one of the following options correctly describes the language accepted by P?

Consider the following languages:

L₁ = {aⁿ waⁿ | w $$\in$$ {a, b}*}

L₂ = {wxw^R | w, x $$\in$$ {a, b}*, | w | , | x | > 0}

Note that w^R is the reversal of the string w. Which of the following is/are TRUE?

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/are FALSE?

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 context-free?

In a pushdown automaton P = (Q, ∑, Γ, δ, q₀, F), a transition of the form,

where p, q ∈ Q, a ∈ Σ ∪ {ϵ}, and X, Y ∈ Γ ∪ {ϵ}, represents

(q, Y) ∈ δ(p, a, X).

Consider the following pushdown automaton over the input alphabet ∑ = {a, b} and stack alphabet Γ = {#, A}.

The number of strings of length 100 accepted by the above pushdown automaton is ______

Consider the following languages.

L₁ = {wxyx | w, x, y ∈ (0 + 1)⁺}

L₂ = {xy | x, y ∈ (a + b)*, |x| = |y|, x ≠ y}

Which one of the following is TRUE?

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

$$\,\,\,\,\,\,\,\,{\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}.\,\,\,\,\,\,\,$$ $$\left\{ {{a^m}{b^n}{c^p}{d^q}} \right.|m = n$$ and $$p=q,$$ where $$\left. {m,n,p,q \ge 0} \right\}$$
$$\,\,\,\,{\rm III}.\,\,\,\,\,\,\,$$ $$\left\{ {{a^m}{b^n}{c^p}{d^q}} \right.|m = n = p$$ and $$p \ne q,$$ where $$\left. {m,n,p,q \ge 0} \right\}$$
$$\,\,\,\,{\rm IV}.\,\,\,\,\,\,\,$$ $$\left\{ {{a^m}{b^n}{c^p}{d^q}} \right.|mn = p + q,$$ where $$\left. {m,n,p,q \ge 0} \right\}$$

Which of the languages above are context-free?

Which one of the following pairs of languages is generated by $${G_1}$$ and $${G_2}$$, respectively?

Here, $${w^r}$$ is the reverse of the string $$w.$$ Which of these languages are deterministic Context- free languages?

Which of the following are FALSE?
$$1.$$ Complement of $$L(A)$$ is context - free.
$$2.$$ $$L(A)$$ $$ = \left( {{{11}^ * }0 + 0} \right)\left( {0 + 1} \right){}^ * {0^ * }\left. {{1^ * }} \right)$$
$$3.$$ For the language accepted by $$A, A$$ is the minimal $$DFA.$$
$$4.$$ $$A$$ accepts all strings over $$\left\{ {0,1} \right\}$$ of length at least $$2.$$

Which of the following statements is not TRUE?

List-$${\rm I}$$
$$E)$$ Checking that identifiers are declared before their
$$F)$$ Number of formal parameters in the declaration of a function agrees with the number of actual parameters in a use of that function
$$G)$$ Arithmetic expression with matched pairs of parentheses
$$H)$$ Palindromes

List-$${\rm II}$$
$$P)$$ $$L = \left\{ {{a^n}{b^m}{c^n}{d^m}\,|\,n \ge 1,m \ge 1} \right\}$$
$$Q)$$ $$X \to XbX\,|\,XcX\,|\,dXf\,|g$$
$$R)$$ $$L = \left\{ {www\,|\,w \in \left( {a\,|\,b} \right){}^ * } \right\}$$
$$S)$$ $$X \to bXB\,|\,cXc\,|\,\varepsilon $$

For the correct string of (earlier question) how many derivation trees are there?

Which of the following strings is generated by the grammar?

Which combination below expresses all the true statements about $$G?$$

Which of the following statement is FALSE?

Which one of the following is TRUE?

Let $${N_a}\left( w \right)$$ and $${N_b}\left( w \right)$$ denote the number of $$a's$$ and $$b's$$ in a string $$w$$ respectively. The language
$$L\left( G \right)\,\,\, \subseteq \left\{ {a,b} \right\} + $$ generated by $$G$$ is

Which one of the following strings is not a number of $$L(M)?$$

($$\varepsilon $$ denotes the null string). Transform the given grammar $$G$$ to an equivalent context- free grammar $${G^1}$$ that has no $$\varepsilon $$ productions ($$A$$ unit production is of the from $$x \to y,\,x$$ and $$y$$ are non terminals).