Log In
2 votes

in Theory of Computation
retagged by

2 Answers

4 votes
Best answer

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

{ aibj | i > j } ∪ { aibj | i < j and 2i > j } ∪ { aibj | 2i < j }

G1 = { aibj | i > j }

G2 = { aibj | i < j and 2i > j }

G3 = { aibj | 2i < j }

G1 and G3 are quite easy to figure out. 
for G1
S →   aSb | aS1
S→ aS1 |ε

for G3
S → aSbb | S1b
S1 → S1b | ε 

Now tricky part is G2.
S → aSb | aS1b
S1 → aS1bb | aS2bb
S2 → ε

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

selected by
5 votes


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 .

edited by

In L1 : {ab | m< n or m>n } and { ab| 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 : {ab | m<n or m>=2n } ---> Hence Language is NCFL.

So option B is correct.


@Gate Mission 1

According to u we can rewrithe L1 : {ab | 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 .


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, {ab | m!=n or m!=2n } is equvalent to {ab | m!=n } is eqivalent to {ab | m< n or m>n } which can be realized using DPDA.

plz correct me!!! 

Related questions

3 votes
1 answer
$L_1 =\{a^n b^m c^n \mid m,n \geq 0\}$ and $L_2=\{ a^n b^n\mid n\geq 0\}$. If $L=L_2-L_1$ then $L$ is finite language regular language DCFL not DCFL
asked Nov 10, 2017 in Theory of Computation Prateek Raghuvanshi 142 views
4 votes
2 answers
$L1= \{a^mb^nc^k\;|\;if\,(m=n)\,then\,(n!=k)\} \\ L2= \{a^ib^jc^k\;|\;if\,(i<j)\,then\,(k<j)\}\\ L3= \{a^ib^jc^k\;|\;(i<j)\,\leftrightarrow \,(k<j)\}$ Could someone please help to conclude the class of above languages? Below mentioned is the logic used to conclude that L1 and L2 are CFL but ... ( i<j) and comp( k<j) ] or [ (i<j) and (k<j) ] = [ (i>=j) and (k>=j) ] or [ ( i<j) and ( k<j) ] = CSL
asked Nov 17, 2016 in Theory of Computation yg92 512 views
3 votes
1 answer
Is the language $L=\left \{ (0^{n}1^{n})^{*} |n\geq 0 \right \}$ is DCFL ?
asked Oct 21, 2016 in Theory of Computation saurabh rai 485 views