Question

L ={x^a y^b z^c | c=a+b}

a) Prove that L is not regular.

b)Prove by giving a context-free grammar that the L is context free.

c)Give a regular expression of the complement L'.

Answer 1

****************Please provide feedback for any issue in solution. Thanks ****************

Note: A language is regular or not can be done using pumping lemma. Pumping Lemma is tough to explain that why i deferred using it. I even didn't come across a easy and good explanation using pumping lemma.

SOLUTION

Part a) The L is not regular because c=a+b in consists of counting i.e. a+b is equal to c, require maintaining sum of a+b, with c

This can be achieved only using a stack see image below for example w=abcc .

The stack pushes a and b into the stack whenever a c encountered on element is popped. If during course of scanning string, end of input is reached without a empty stack sting is not accepted. otherwise an empty stack with end of input designates string acceptance.Rest cases where either stack is empty or input string is completely scanned the string is rejected.

=================================================================

part b)

where A is start symbol and is null string.

=====================================================================

part c)

complement of is does not have a regular expression. If this has been the case would have been regular too.

Regular languages are closed under complementation. If is regular than complement of which is . would be regular which we prove to not regular.