edited by
322 views

1 Answer

2 votes
2 votes

$B$ can be written as $B=\{a^{i}b^{i}c^{+}+a^{i}b^{+}c^{i}|~i\ge0\}$. [Note that '$+$' is OR not PLUS].

$\therefore B=\{abc, aabbc, aabcc, aabbcc,...\}$

Here, $B$ is not regular as there is no counting mechanism in DFA for $a^{i}b^{i}$ or $a^{i}\_~c^{i}$. But $B$ is a Context Free Language (CFL) as it can be constructed using Push Down Automata(PDA) by the following grammar.

$\begin{align} S &\to AC~|~D\\ A &\to aAb~|~ab\\ B &\to bB~|~b\\ C &\to cC~|~c\\ D &\to aDc~|~aBc  \end{align}$

But this language $B$ is not a Deterministic Context Free Language (DCFL).

To proof this, just take the string $aabbcc$ from $B$.
Clearly $S \to AC$ can produce it and also $S \to D$ can produce it. So there are two different ways of parsing the string. It means in the Push Down Automation, we have two different cases like below. That's why it's non-deterministic.

 

Case 1 Case 2
$\mathrm{PUSH~}a\\\mathrm{PUSH~}a\\\mathrm{POP~}b\\\mathrm{POP~}b\\\mathrm{PUSH~}c\\\mathrm{POP~}c\\$ $\mathrm{PUSH~}a\\\mathrm{PUSH~}a\\\mathrm{PUSH~}b\\\mathrm{POP~}b\\\mathrm{POP~}c\\\mathrm{POP~}c\\$

 

In the table, we notice after pushing $a$ twice, there are two different cases whether to pop or push $b$ showing the non-determinism.

 

$\therefore B$ is not a DCFL.

 

edited by

Related questions

0 votes
0 votes
1 answer
4