ME-FST1-Q51

Question

I have a little doubt regarding the Language L.Any one please what L contain?

Comments

L1 = epsilon, ac,b,abc ...

L2=epsilon , ab,aabb....

L1-L2 =ac,b,abc,..... L1 only except epsilon...

Answer 1

Here, L1 = { aⁿb^mcⁿ  | n,m>=0 }

         L2 = { aⁿbⁿ     | n >=0 }

L = L1 - L2

   = L1 intersection L2^c .  // L2^c => { aⁿb^m     | n,m >=0 and n !=m }

   =  aⁿb^mcⁿ - epsilon. | n,m >=0.

Here L is a DCFL.

Equivalent DPDA for L is,

Comments

Q0 to Q3 -> (b,z,bz)

Q3 to Q3 -> (b,b,bb), right ?

---

Why ?

I think, we don't need to count no of b's, so no need to push b's on stack. ... just read it and move ahead.

Answer 2

First of all we know :

 Identifying the resultant language :

L₁ - L₂ means string is in L₁  but not in L₂ ..Means this set will not contain the strings which have equal number of a's followed b's.So in short only those strings will contain which have either equal number of a's followed by c's and no of b's in between or any non zero number of b's..Thus we obtain the resultant language as {aⁿb^mcⁿ|n >= 1,m >=0 } ∪ {bⁿ | n >= 1} [as epsilon is a part of L2]  which is a DCFL..

This way we can also deduce that the language given in the question is a DCFL..Hence C) is the correct answer..

But this method requires correct identification reasoning ..Then only we can arrive at the correct answer..If we are not able to get the idea about what type of strings will be generated , it is better to go with the original method which is discussed earlier..

Comments

Corrected .. Plz have a look..

---

Habib,all strings $\big \{ abb, aaa, bbb \big \}$ belongs to $L2^c$. So i think regExp $(a+b)^*ba(a+b)^*$ is wrong.

---

Ok a⁺ and b⁺ part is missing in the regular expression.. Adding it.. Too many silly mistakes in 1 question ..:) Correcting..