DCFL not closed under

Question

DCFLs are not closed under ________

a. Complement operation

b. Inverse homomorphism operation

c. Reversal operation

d. Prefix operation

Answer 1

DCFL closed under right quotient (suffix)  

So option should be c

https://math.stackexchange.com/questions/871662/finding-right-quotient-of-languages

Answer 2

REVERSAL

Comments

@meghna dcfl is NOT closed under concatenation.

---

@brij mohan, yes absolutely correct.

---

@Arpon Could you give any example for DCFL being not closed? I couldn’t think of any!

Edit: Found an example.

From https://www.cs.wcupa.edu/rkline/fcs/cfl-pump.html

The problem is that a string in the first language loses the presence of the "$" marker. For example, consider the concatenation of these two DCFLs:

{ambn: m < n} · { wcwR: w ∈ {a,b}* }

This string abbb·bbbacabbb is accepted, but how would you know on which b you should "jump across" from one language to the other and stop consuming the b and start stacking it?

Answer 3

c) reversal operation : consider the expression  "wcw^rx" ,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 "xw^rcw" here we can see that the DPDA won't be able to accept the language because of the ambiguity.

 

Comments

since you didn't specified domain of w,c and x. I am assuming that c,x are identifiable by the machine (as you wrote push w, skip c, pop w^r, skip x)

what is the ambiguity here??? how its not acceptable by dpda??

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

---

Here w , wr ,x belongs to (a+b)* and c is any symbol other than a or b...

---

The reverse is dcfl because if we write xw^rcw then w^r can easily logiced.like ignore x then push w^r then ignore c then pop w.r.t. w

Answer 4

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.

Comments

can you explain how?

---

I included explanation in my answer. Reply if anything is unclear.