Context free language

Question

Answer 1

L2 is dcfl and L1 is Cfl
soln for L2  Let E = { aⁱb^j  | i ≠ j and 2i ≠ j }
Split it as unions of  3 languages.

{ aⁱb^j | i > j } ∪ { aⁱb^j | i < j and 2i > j } ∪ { aⁱb^j | 2i < j }

G¹ = { aⁱb^j | i > j }

G² = { aⁱb^j | i < j and 2i > j }

G³ = { aⁱb^j | 2i < j }

G¹ and G³ are quite easy to figure out. 
for G¹
S →   aSb | aS¹
S¹ → aS¹ |ε

for G³
S → aSbb | S¹b
S¹ → S¹b | ε 

Now tricky part is G2.
S → aSb | aS¹b
S¹ → aS¹bb | aS²bb
S² → ε

note- L2 is  given as problem 2.24 in shipser book.

Answer 2

L1= CSL

why ? because  two comparison at a time which is not possible with a stack so its csl if it were written as
M!=n OR M!=2n then it will be CFL .

L2 is DCFL so CFL also 

why ? because we can accept every string in l2 language deterministically push a's into stack when b's comes start poping it aftet that accept it.

so A) option true .

Comments

In L1 : {aⁿ b^m  | m< n or m>n } and { aⁿ b^m | m <2n or m>2n }

Here and is nothing but intersection in two sets :

m<n intersection m<2n gives --> m<n 

m>n intersection m>2n gives --> m>=2n

So L1 : {aⁿ b^m  | m<n or m>=2n } ---> Hence Language is NCFL.

So option B is correct.

---

@Gate Mission 1

According to u we can rewrithe L1 : {aⁿ b^m  | m<n or m>=2n } 

but check string aabbb is not accepting in ur language while it is accepting in given L1 in question.

n=2 m=3

3<2 or 3>=4 (both are false) // so ur language wont accept

---

@Rajesh Pradhan. thanks for example.

Agreed i gave wrong language. Can you tell me where did i messed up in my solution ?

---

@kunal chalotra plz explain about L1

Q1. if it is csl then plz explain how we accept this using 2 stack. (I know it is possible but i m not getting the procedure right now)

Q2."if were written as  m!=n OR m!=2n then it will be CFL " how this possible using single stack.

Thanks in advance.

---

@rajesh  bro .acc to gate point of view i have solved previous year with basics identification properties only .the thing which u r asking i myself don't know :( how it will be actually be done  using two stacks.

for q2 : for making NPDA of m!=n OR m!=2n, at every step of the transition we will have two copies  one for PUSH and one for POP with this way we will be able to accept the string non deterministically making its cfl .

---

@kunal 

for q2 : for making NPDA of m!=n OR m!=2n  (I think it should be DPDA instead of NPDA)

first, we have to push all a's into the stack and when b arrives pop a for each arrival of b 

case 1:- if b still coming while stack is empty (all a poped) THEN m!=n Condition True and we wont check m!=2n.

case 2:- if b over and at the same time the stack is empty means m=n (Now here imp. point is if m=n then m!=2n is always true so no need to check m!=2n)

Note:- My point is we never going to check here m!=2n condition So we can find here deterministically by just checking no of a's are equal to no. of b's or not which makes it DPDA.

Finally, {aⁿ b^m  | m!=n or m!=2n } is equvalent to {aⁿ b^m  | m!=n } is eqivalent to {aⁿ b^m  | m< n or m>n } which can be realized using DPDA.

 https://gateoverflow.in/30897/if-l2-is-dcfl-how-to-draw-its-dpda

plz correct me!!!