retagged by
1,134 views
5 votes
5 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
retagged by

2 Answers

Best answer
5 votes
5 votes

L1={ambnck|if(m=n)then(n!=k)

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

L3={aibjck|(i<j)↔(k<j)}.....
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 votes
1 votes

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.

Related questions

3 votes
3 votes
1 answer
2
Prateek Raghuvanshi asked Nov 10, 2017
488 views
$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$ isfinite languageregular languageDCFL not DCFL
2 votes
2 votes
2 answers
3
3 votes
3 votes
1 answer
4
saurabh rai asked Oct 21, 2016
1,106 views
Is the language $L=\left \{ (0^{n}1^{n})^{*} |n\geq 0 \right \}$ is DCFL ?