edited by
8,940 views

4 Answers

1 votes
1 votes
REVERSAL
1 votes
1 votes

c) reversal operation : consider the expression  "wcwrx" ,its a DCFL because it can be easily accepted by DPDA.

  • push w
  • bypass c
  • pop w^r
  • bypass x

Now as we reverse the expression what we have is "xwrcw" here we can see that the DPDA won't be able to accept the language because of the ambiguity.

 

0 votes
0 votes

C, reversal operation.

Let G(V,T,S,P) be DCFL grammar, then

G(V,T,S,Pr) be the reversal of grammar G.

which can either be DCFL or NCFL. Hence, under reversal operation, DCFL are not closed.

EXAMPLE

L = {ac^n b^n} U {c^k b^2k}, this is DCFL as push & pop operation is haing no ambiguity.

The grammar for above language is (consider $ as NULL),

S->Y/Z

Y->aA

A->cAb/$

Z->cZbb/$

Now

Reverse the grammar,

S->Z/Y

Z->bbZc/$

Y->bAca/$

Corresponding reversed L will be,

L(reversal) = {b^2k c^k} U {b^n c^n a}, this becomes NCFL as after pushing b’s it will be ambiguous to compare it with c^k OR c^n.

edited by

Related questions

4 votes
4 votes
2 answers
2
srestha asked Jun 22, 2018
1,532 views
$\left \{ a^{m+n}b^{m+n}c^{n}|m,n\geq 1 \right \}$$\left \{ a^{m+n}b^{m+n}c^{k} |m,n,k\geq 1\right \}$$\left \{ a^{m+n}b^{m+k}c^{n+k} |m,n,k\geq 1\right \}$Which one DCFL...
1 votes
1 votes
1 answer
3
pranab ray asked Dec 9, 2017
664 views
0 votes
0 votes
1 answer
4
shivangi5 asked Dec 2, 2017
852 views
Consider the following languages:L1={abna2n|n>=0}L2={aabna3n|n>=0}Why L1UL2 is DCFL please explain?