Log In
4 votes
$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 L3 is CSL but have noticed in most solutions L1 is treated as CSL. Could someone kindly point the flaw in below mentioned logic?

p implies q. If p then q. p -> q.

L1 = comlement(p) or q

     = complement(m=n) or n!=k.  

    = m!=n or n!=k

L1 = { aabbccc, aabbbccc, aabbbcc.. } = NCFL

We can have union of two PDA's. One will accept the strings whenever m!=n and the other will accept the strings only when n!=k

L2 = comlement(p) or q

     = complement( i< j ) or k<j.  

    = i>=j or k<j

L2   = { aabc, abbccc. } = NCFL

We can have union of two PDA's. One will accept the strings whenever i>=j and the other will accept the strings only when k<j

$L3 = p \leftrightarrow q\\ \;\; \overline{p}\;\overline{q}\;+\;pq$

      = [ comp( i<j) and comp( k<j) ] or [ (i<j) and (k<j) ]

      = [ (i>=j) and (k>=j) ] or [ ( i<j) and ( k<j) ]

     = CSL
in Theory of Computation
retagged by
all are CSL's ?
i am now confused here .need expert @arjun sir or @parveen sir

Kindly, have a look at this question in which L2 is said to be CSL and selected correct.

2 Answers

5 votes
Best answer


check the condition if P then Q

can be written as -P V Q.....means either -P(m!=n) should be true at a time or Q(n!k)
SO this is a CFL

L2={aibjck|if(i<j)then(k<j)}...same way...CFL

check for condition..........(P<->Q)
means P->Q &Q->P
means(-P V Q) & (-Q V P)...because of this "&" we need to check 2 conditions at a time...not possible with 1 stack....

SO 1,2 are CFL...3 is not a CFL

edited by
1 vote

I am getting all as CFL's.

I can't comment on your logic as i have not studied propositional logic.

For L1: L1={ambnc| if(m=n)then(n!=k) }

to check equal a and b we need a stack where we first push all a's then we pop an 'a' on seeing a 'b'. So 'm=n' condition satisfies when stack is empty and we have no more b's to see. But now to check 2'nd condition i.e n!=k, we should have track of b's which we lost while comparing with a's hence with one stack we cannot process this language. Hence it;s not CFL rather CSL.

Similarly in L2 when we compare i and j we lost some b's i.e we don't have exact track of b's so to do next comparison k < j, we need another stack, hence not cfl rather CSL.

Similarly for L3 one stack insufficient.

Hence all languages are CSL.

@Gate Mission 1 Thank you for the solution. But I still feel using propositional logic we can conclude that first two languages are CFL. @Arjun Sir Could you please check this question once and confirm the class of language?
@yash mathematics never lies. You are correct.
@arjun sir you mean to say L1 and L2 are cfl's ?
Thank you Arjun Sir for the confirmation.

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 141 views
2 votes
2 answers
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