482 views
2 votes
2 votes

Let $\sum = \{0,1\}$

  1. Let  $A=\{0^{k}u0^{k}|k\geq 1$ $\text{and}$ $u\in \sum^{*}\}.$ Show that $A$ is regular.
  2. Let  $B=\{0^{k}1u0^{k}|k\geq 1$ $\text{and}$ $u\in \sum^{*}\}.$Show that $B$ is not regular.

2 Answers

0 votes
0 votes
option (a) is regular. it's a language which start with 0 and end with 0.

 
option b is not regular because of after 1 how can you find the difference between u and 0.
edited by
0 votes
0 votes

a.)    As, it can be clearly seen that  A recoginzes all strings started and ends with a   “0” .

        therefore, it is Regular Language 

b.)    Language B can be proved as non regular language 

       

  by Myhill – Nerode Theorem , 

 

       suppose set, S = { 01, 001, 0001 ….  (0^k)1 ,...}

               and, z = 0^k 

 

       Now, take  two pairs of set S to prove that they are distinguishable  i.e, → 0^k1 , 0^n1

 

        ..    As , (0^k)(z) = (0^k1)0^k   { which is accpeted by L(B) }

             and, (0^k)(z) = (0^n1)0^k   {  which is not accepted by L(B) }

 

          As, by def. of Myhill- Nerode Theorem,

 

     there are infinite distinguishable equivalence strings { corresponding to elements in S }

  •       which results in B as non regular language

Related questions

1 votes
1 votes
0 answers
4