Recent questions tagged grammar

Consider the grammar $$S\rightarrow aS\mid Sb\mid b$$ Which of the following statements are correct?The given grammar is a Type $3$ grammar. The given grammar is a Type $...

Consider the right-linear grammar,$$\begin{aligned}A &\to fB \mid gA \\B &\to gA \mid fC \mid f \\C &\to gA \mid fC \mid f\end{aligned}$$When this grammar is converted in...

Which of the following statements are correct for converting a finite automaton into an equivalent right-linear grammar?Each automaton state becomes a non-terminal. The s...

Consider the NFA given below: Which right-linear grammar is obtained by the standard NFA-to-grammar construction?$q_0 \to aq_1$,$q_1 \to aq_0 \mid bq_1 \mid \epsilon$ $q_...

Consider the right-linear grammar,$$\begin{aligned}S &\to aB \mid bS \mid \epsilon \\B &\to aS \mid bB\end{aligned}$$Which NFA is obtained by the standard grammar-to-NFA ...

Consider the right-linear grammar,$$\begin{aligned}S &\to aT \\T &\to abcS \mid b\end{aligned}$$If this grammar is converted into an NFA with one input symbol per transit...

Consider the grammar $G$ with productions :$$\begin{aligned}S &\to aB \mid \epsilon \\B &\to Sbb\end{aligned}$$Which option is correct?$L(G)=\{a^n b^{2n}\mid n\ge 0\}$ an...

Consider the grammar $G$ with start variable $A$ and productions $:$$$\begin{aligned}A &\to aB \mid bC \\B &\to aB \mid \epsilon \\C &\to aD \mid A \mid bC \\D &\to aD \m...

Given below are two statements: one is labelled as Assertion A and the other is labelled as Reason RAssertion A: $L=\left\{a^{n} b^{n} c^{n}: n \geq 0\right\}$ is accepte...

Match List I with List II$\begin{array}{|ll|ll|} \hline & \textbf{List I} & & \textbf{List II} \\ \hline \text{A.} & \text{Type } 3 \text{ Grammar} & \text{I.} & \mathrm...

Match the $\textbf{LIST-I}$ with $\textbf{LIST-II}$$\begin{array}{|l|l|l|l|} \hline & \textbf{ LIST-I } & & \textbf{ LIST-II } \\ \hline \text{A.} & \text{Type} - 0 \text...

Consider the Grammar:\[\begin{array}{l} \mathrm{S} \rightarrow \mathrm{~A} \\ \mathrm{~A} \rightarrow \$ \mathrm{~B} \$ \mid \mathrm{id} \\ \mathrm{~B} \rightarrow \mathr...

Consider the Grammar:$\begin{array}{l}\mathrm{T} \rightarrow \mathrm{Q} x \\\mathrm{Q} \rightarrow \mathrm{RS} \\\mathrm{R} \rightarrow \mathrm{y} \mid \varepsilon \\\mat...

Which of the following are context free language?$\left\{\mathrm{w}^{\mathrm{i}} \mathrm{x}^{\mathrm{j}} \mathrm{y}^{\mathrm{k}} \mathrm{z}^{l} \mid \mathrm{i}+\mathrm{k}...

Let $\text{L}=\{a b, a a, b a a\}$. Which of the following strings are not in $\text{L}^{*}$.$\mathrm{abaabaaabaa}$$\mathrm{aaaabaaaa}$$\mathrm{baaaaabaaaab}$$\mathrm{baa...

Consider two grammars $G_{1}$ and $G_{2}$ with the production rules given below: $G_{1} : S \rightarrow$ $if$ $E$ $then$ $S$ $|$ $if$ $E$ $then$ $S$ $else$ $S$ $|$ $a$ ...

Let $\Sigma=\{a, b, c\}$. What is the language generated by the following grammar?\[S:=\epsilon|a S| S b \mid c S\]$(a+b+c)^{*} b^{*}$$(a+b+c)^{*} c^{*}$$(a+c)^{*} b^{*}$...

Let $\Sigma=\{a, b\}$ be an alphabet. A palindrome is a word which reads the same when read from left-to-right, or from right-to-left. For example, the words $a b b a, a ...