Question: We know that the language AiBiCi = { a ^ ib ^ ic ^ i | i > = 0 } is not context -

We know that the language AiBiCi ={a^ib^ic^i | i>=0} is not context-free. Show that the complement of AiBiCi is context-free. We can break it down into four cases:
(1) w is in a*b*c*, but the number of a's and the number of b's in w are not equal,
(2) w is in a*b*c*, but the number of b's and the number of c's in w are not equal,
(3) w is in a*b*c*, but the number of a's and the number of c's in w are not equal,
(4) w is not in a*b*c*.
Show that each of the four cases are context-free, then since the context-free languages are closed under union, the complement of AiBiCi must be context-free.

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Programming Questions!