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

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

Regularity is preserved under the operation of string reversal.

All subjects of regular sets are regular.

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

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

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

Which of the following strings is generated by the grammar?

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

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

Which of the following statement is FALSE?

Which one of the following is TRUE?

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

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

($$\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).