413 views
2 2 votes

Consider the following languages over the alphabet $\{a, b, c\}$ :

  • $L_1=\left\{w c w \mid w \in\{a, b\}^*\right\}$
     
  • $L_2=\left\{w c w^R \mid w \in\{a, b\}^*\right\}$
     
  • $L_3=\left\{w w^R \mid w \in\{a, b\}^*\right\}$

Which one of the following statements is TRUE?

  1. $L_2$ IS A CFL, BUT NOT A DETERMINISTIC CFL.
     
  2. $L_3$ IS A DETERMINISTIC CFL.
     
  3. $L_1$ IS A CONTEXT-FREE LANGUAGE.
     
  4. $L_2$ IS A DETERMINISTIC CFL, BUT $L_1$ IS NOT A CFL.

3 Answers

0 0 votes
We know, DCFL is a subset of CFL.

For a language to be DCFL, it has to be accepted by a DPDA (Deterministic Pushdown Automata) i.e. for every input symbol and stack symbol, atmost one possible move.

For DCFL: 1) Machine can predict what to do next without guessing.

                  2) Strings can be parse left to right unambigiously.

For non-DCFL: 1) Machine need to guess a point or symbol.

                         2) The grammar or parse tree is ambigious or requires epsillion-transitions that lead to non determinism.

Analysing each language, L1 = {wcw | w belongs to {a,b}*}, in the given language -----------c----------------- no of characters before c = no of characters after c. Since machine has to remember th previous one therefore it cannot be context free language.  If its not CFL, there's no question of DCFL and NON DCFL.

Analysing other langiage, L2 = { wcw^R|w belongs to as pervious one}, in the given language R claraly states that after c there has to be the reverse order of the w. The machine remembers w on the stack; it only needs guessing if the separator is not unambiguously marked., and,  as it has to remember the point about which the reverse must happen, it is deterministic CFL.

Analysing another option, L3 = {ww^R| w belongs to as previous one} in the given language there's no point about which machine knows wether to stop popping or start therefore it is not a DCFL. But it is CFL.
Answer:
Position:
Show:

Related questions

3 3 votes
3 3 answers
570
570 views
GO Classes asked Nov 4, 2025
570 views
Consider a Deterministic Finite Automaton (DFA) $M=\left(Q, \Sigma, \delta, q_0, F\right)$ where:$\Sigma=\{a, b\}$ $Q=\left\{S_0, S_a, S_b, S_{e r r}\right\}$ $q_0=S_0$ $...
1 1 vote
1 1 answer
236
236 views
GO Classes asked Nov 4, 2025
236 views
Consider the following decision problems:(P1) : Given a Context-Free Grammar $G$ and a regular expression $R$, is the language $L(G) \backslash L(R)$ also a Context-Free ...
1 1 vote
1 1 answer
282
282 views
GO Classes asked Nov 4, 2025
282 views
Let $\mathbb{N}=\{1,2,3, \ldots\}$ be the set of natural numbers. Let $\Sigma=\{a, b\}$ be an alphabet.Which of the following statements is/are TRUE?THE SET OF ALL LANGUA...
1 1 vote
3 3 answers
369
369 views
GO Classes asked Nov 4, 2025
369 views
Consider the following context-free grammars:$$\begin{aligned}& G_1: S \rightarrow A|B, A \rightarrow a A| a, B \rightarrow b B \mid b \\& G_2: S \rightarrow A B, A \righ...