The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+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

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

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.

+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**

+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={a ^{m}b^{n}c^{k }| 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.**

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.3k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.1k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.6k
- Others 1.8k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,339 questions

55,765 answers

192,356 comments

90,817 users