Mumbai University > Computer Engineering > Sem 4 > Theoretical Computer Science

Marks: 5M

Year: May 2016

1. we dont know m, but assume there is one
2. Choose a string w=0^i where i is a prime number and |xyz|=n>m+1(This can always be done because there is no largest prime number) Any prefix of w consists entirely of 0's.
3. We dont know the decomposition of w into xyz but since |xy|<=m it follows that |z|>1. As usual |y|>0.
4. Since |z|>1, |xz|>1. Choose i=|xz|.
5. Then |xy^iz|=|xz|+|y||xz|=(1+|y|)|xz|.
6. Since (1+|y|) and |xz| are each greater than 1, the product must be a composite number.
7. Thus |xy^iz| is a composite number. Hence, the give language is not regular.