1 vote
1 vote
Can we construct finite automata for

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

4 Comments

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

@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.

0
0

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\}$
0
0

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.