# Identifying Context Free Language

509 views
$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
0
all are CSL's ?
0
i am now confused here .need expert @arjun sir or @parveen sir
0

Kindly, have a look at this question https://gateoverflow.in/30669/identify-whether-language-context-free-context-sensitive in which L2 is said to be CSL and selected correct.

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 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.

0
@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?
0
@yash mathematics never lies. You are correct.
0
@arjun sir you mean to say L1 and L2 are cfl's ?
0
yes..
0
Thank you Arjun Sir for the confirmation.

## Related questions

1
269 views
Is B context free? Please explain in detail.
$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
Is the language $L=\left \{ (0^{n}1^{n})^{*} |n\geq 0 \right \}$ is DCFL ?