1 vote
1 vote
Can we construct finite automata for

The numbers 1,2,4...2^n,.... Written in unary
in Theory of Computation


No, it is a non-regular language
Could you please explain why it is not regular

@pranita-parab because for infinite language to be a regular there must exist some pattern so we can depict that by using loop in DFA but there’s no pattern that we can remember using DFA in above language.


Few Questions:

  1. What is the meaning of “pattern” here ?
  2. Whether 2,4,8,... is considered a “pattern” or not for the given language ?
  3. What is the “pattern” present in $\Sigma^* \ ?$ where $\Sigma = \{a,b\}$

1 Answer

3 votes
3 votes

Consider, input alphabet $\Sigma = \{1\}$

So, set $L = \{1,11,1111,11111111,...\} =  \{1^{2^n } \ | \ n \geq 0  \} $

You can prove the $L$ to be non-regular set by Pumping Lemma.

If $L$ is a regular set then 

$\exists \ p$ such that $\forall z \in L, $ where $|z| \geq p$ ( $p$ is the number of states in the finite state machine for $L$, it is also called as pumping length.)

$\exists \ v,w,x$ such that $z = vwx$ and $|vw| \leq p \ ; |w| \geq 1$  and 

$\forall \ i\geq 0, vw^ix \in L$

This is called the pumping property.

If $L$ is a regular set then it must satisfy the pumping property but it can be shown that it does not satisfy the pumping property by a contradiction.

Suppose, $L$ is a regular set.

Consider an element of this regular set as $z = 1^{2^{p-1}} 1^{2^{p-1}} \ $ with  $p \geq 1$

Here, $z \in L$ and $|z| \geq p$

Now, try to decompose $z$ as $z = vwx = 1^a1^b11^{2^{p-1}-a-b-1} 1^{2^{p-1}} \ $ for $a,b \geq 0$ with

$v = 1^a , w= 1^b1, x = 1^{2^{p-1}-a-b-1} 1^{2^{p-1}}$

Here, $|vw| \leq p$ and $|w| \geq 1$

Now, pump $z$ two times i.e. for $i=2,$ $vw^ix$ is:

$vw^2x =1^a(1^b1)^2  1^{2^{p-1}-a-b-1} 1^{2^{p-1}}= 1^a 1^b11^b11^{2^{p-1}-a-b-1} 1^{2^{p-1}} = 1^{2^p +b+1}$ 

For $b=2, \ z = 1^{2^p+3} \notin L$ 

But according to pumping lemma, $z$ should be in $L.$ So, Contradiction. 

Hence, $L$ is not a regular set.