The Gateway to Computer Science Excellence

+16 votes

Best answer

+8 votes

Complement will include all strings which are not in the given language like $\{a,b,c,ab,ac,ba,bc,cba,aaabbc, \dots\}$

$(a^nb^nc^n)^c = \Sigma^* - (a^nb^nc^n)$

$= \underset{\text{CFL}}{\left\{a^pb^qc^r \mid p\neq q \text{ or } q\neq r \right\}} \cup \underset{\text{Regular}}{ \left\{(a + b + c)^* ( ba + ca + cb + cba ) (a+b+c)^*\right\}}$

Therefore It is a CFL as CFLs are closed under union (when we do union operation over two CFLs, we always get a CFL).

0

Language containing equal number of a's b's and c's....is it a^{n}b^{n}c^{n} ..?

the question doesn't mention anything about the order of a's b's and c's ...the above said language can be any one of the form c^{n}a^{n}b^{n }OR b^{n}a^{n}c^{n} OR c^{n}b^{n}a^{n}...

Please clarify...

+2

I think NO, equal no of a's , b's and c's mean they may be in any order, $a^nb^nc^n$ is a subset of it.

0

Abhay wt u told is correct .but still some strings is missing for eg "aabcbcacb" this order is not satisfied by any of the above mentioned string told by u.

0

kunal , you are right... In the string with equak number os a's b's and c's , the order of a,b,c are not important.

Please refer comment from Umang Raman. that is correct to me.

0 votes

instead of doing all that,language is {a^nb^nc^n/n>=0}

to construct pda for this language.**logic is** for single 'a' push two 'a' s into the stack when it sees 'b' s and 'c' s pop it from stack.

equall number of 'a' s ,'b' s and 'c' s condition is satisfied.so this language is **dcfl,complement of DCFL is also DCFL.**

0

a^n b^n c^n it means equal no of a's b's and c's

what are you going to do with aabbbc

this string is not in the language but a/c to your approach which is push 2 a's instead of 1 a .this string is going to be accepted.

how ===>push 2 a's for first a then again push 2 a's for next a then pop 3 a's with each b and in last pop last a with c it is accepted but this string is not in the language.

so your approach is failed here.

what are you going to do with aabbbc

this string is not in the language but a/c to your approach which is push 2 a's instead of 1 a .this string is going to be accepted.

how ===>push 2 a's for first a then again push 2 a's for next a then pop 3 a's with each b and in last pop last a with c it is accepted but this string is not in the language.

so your approach is failed here.

0

k,i have another doubt

L={a^nb^nc^n/n>=0} is **CONTEXT SENSITIVE LANGUAGE**.SO COMPLEMENT OF CSL IS MAY OR MAY NOT BE CSL,HOW CAN WE SAY THAT IT IS ACCEPTED BY NPDA.PLEASE CLARIFY MY DOUBT

0

its a CSL and we know by closure property that CSL are closed under complementation

so it should be CSL

but we can draw PDA for its complement by making a is not equals to b or b is not equals to c or a isnot quals to c so it is CFL too

so it should be CSL

but we can draw PDA for its complement by making a is not equals to b or b is not equals to c or a isnot quals to c so it is CFL too

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

50,650 questions

56,193 answers

193,988 comments

94,863 users