Given the following two statements : A. L = {w|na(w) = nb(w)} is deterministic context free language, but not linear. B. L = {an bn} ∪ {an b2n} is linear, but not deterministic context free language. Which of the following options is correct ?
Both (A) and (B) are true.
A linear grammar has at most one variable on the right-hand side of every production. A deterministic context free language (DCFL) is one accepted by a deterministic pushdown automaton (DPDA) by final state.
Statement A — For L = {w | na(w) = nb(w)} a DPDA keeps the running surplus of a's or b's on its stack: it pushes a symbol for the letter in excess, pops when the opposite letter arrives, and enters an accepting state whenever the stack is back to its bottom marker. Every move is forced, so L is a DCFL. It is a standard result (Linz, exercises on linear languages) that L is not linear: a linear grammar can only generate matched pairs from the two ends of the string inward, which cannot track arbitrary interleavings such as (ab)k(ba)k. Statement A is true.
Statement B — The grammar S → A | B, A → aAb | λ, B → aBbb | λ is linear and generates {anbn} ∪ {anb2n}. A DPDA, however, must decide while reading the b's whether to match one or two b's per a; after reading anbn it must both accept and still be able to continue towards anb2n, which is the textbook example (Hopcroft–Ullman) of a language that is context free but not deterministic. Statement B is true.
Since both statements hold, the choices saying that either or both are false do not fit.
Both (A) and (B) are true. option is correct.
Similar Questions
According to pumping lemma for context free languages :
Let L be an infinite context free language, then there exists some positive integer m such that any \(w \in L\) with \(|w| \ge m\) can be decomposed as \(w = uvxyz\)
Consider a language A defined over the alphabet \(\Sigma = \{0, 1\}\) as \(A = \left\{0^{\lfloor n/2 \rfloor} 1^{n} : n \gt = 0\right\}\).
The expression \(\lfloor n/2 \rfloor\) means the floor of n/2, or what you get by rounding n/2 down to the nearest integer.
Which of the following is not an example of a string in A ?
Given the following two languages :
\(L_{1} = \{a^{n}\, b\, a^{n} \mid n \gt 0\}\)
\(L_{2} = \{a^{n}\, b\, a^{n}\, b^{n+1} \mid n \gt 0\}\)
Which of the following is correct ?
Which of the following are context free language ?
(A) {wi xj yk zl | i + k = j + l, where i, j, k, l ≥ 0}
(B) {wi xj yk zl | i = j and k = l, where i, j, k, l ≥ 0}
(C) {wi xj yk zl | i = j = k and k ≠ l, where i, j, k, l ≥ 0}
(D) {wi xj yk zl | i = j = k + l, where i, j, k, l ≥ 0}
(E) {wi xj yk zl | i = j = l and k ≠ l, where i, j, k, l ≥ 0}
Choose the correct answer from the options given below :
If L1 and L2 are context free languages, which of the following is True about L1∩L2 ?
In Pumping Lemma for context free languages, to say a language is satisfying pumping lemma, what is the minimum length of ‘vx’ together, if you consider the string as ‘uvwxy’?
Let L = {0n1n|n ≥ 0} be a context free language.
Which of the following is correct ?
Given the following two languages :
L1 = {an bn | n ≥ 0, n ≠ 100}
L2 = {w ∈ {a, b, c}*| na(w) = nb(w) = nc(w)}
Which of the following options is correct ?
Important Questions from Context Free Languages
- Let $\Sigma = \{a, b, c, d\}$ and let $L = \{a^ib^jc^kd^\ell \mid i, j, k, \ell \ge 0\}$.
Which of the following constraints ensure(s) that the language $L$ is context-free? According to pumping lemma for context free languages :
Let L be an infinite context free language, then there exists some positive integer m such that any \(w \in L\) with \(|w| \ge m\) can be decomposed as \(w = uvxyz\)
Consider a language A defined over the alphabet \(\Sigma = \{0, 1\}\) as \(A = \left\{0^{\lfloor n/2 \rfloor} 1^{n} : n \gt = 0\right\}\).
The expression \(\lfloor n/2 \rfloor\) means the floor of n/2, or what you get by rounding n/2 down to the nearest integer.
Which of the following is not an example of a string in A ?
Given the following two languages :
\(L_{1} = \{a^{n}\, b\, a^{n} \mid n \gt 0\}\)
\(L_{2} = \{a^{n}\, b\, a^{n}\, b^{n+1} \mid n \gt 0\}\)
Which of the following is correct ?
Which of the following are context free language ?
(A) {wi xj yk zl | i + k = j + l, where i, j, k, l ≥ 0}
(B) {wi xj yk zl | i = j and k = l, where i, j, k, l ≥ 0}
(C) {wi xj yk zl | i = j = k and k ≠ l, where i, j, k, l ≥ 0}
(D) {wi xj yk zl | i = j = k + l, where i, j, k, l ≥ 0}
(E) {wi xj yk zl | i = j = l and k ≠ l, where i, j, k, l ≥ 0}
Choose the correct answer from the options given below :
