Ask
Login
0
2.7kviews
Show that language L={0^i | i is prime number} is not regular
written 8.7 years ago by gravatar for teamques10 teamques10 ★ 70k •   modified 3.8 years ago

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

Marks: 5M

Year: May 2016
theory of computation
ADD COMMENT EDIT
1 Answer
0
272views
written 8.7 years ago by gravatar for teamques10 teamques10 ★ 70k
  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 …

Create a free account to keep reading this post.

and 3 others joined a min ago.

ADD COMMENT EDIT
Please log in to add an answer.