The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+4 votes
445 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
in Theory of Computation by Active (3.1k points)
retagged by | 445 views
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.

2 Answers

+5 votes
Best answer

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

by Boss (19.6k points)
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.

by Active (4.1k points)
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

+2 votes
2 answers
3
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,339 questions
55,765 answers
192,356 comments
90,817 users