retagged by
1,875 views
8 votes
8 votes
Consider the following statement:
$\text{ For all languages }L \subseteq \{0, 1\}^*, \text{ if }L^* \text{ is regular then L is regular.}$
Is the above statement true? Justify your answer.
retagged by

5 Answers

Best answer
12 votes
12 votes

If $\mathbf{L^*}$ is regular, then $\mathbf{L}$ is not necessarily regular.

Let's take one possible example.

Let $\mathbf{\Sigma = \{a\}}$ and consider the language $\mathbf{L = \{ a^{2^n} \mid n \in N \} }$.

This language is not regular

and the language $\mathbf{L^*}$ is the language $\mathbf{a^*}$, which is regular. To see this, notice that since $\mathbf{L}$ contains the string a, the language $\mathbf{L^*}$ contains all strings of the form $\mathbf{a^n}$ for any natural number $\mathbf{n}$.

Hence, Option(2) Need not Regular is the correct choice.

edited by
12 votes
12 votes
No)

consider set of all odd length palindrome=L={0,1,000,111,101,010,.......}

L*=(0+1)*

Here.L* is regular but L is not regular.
7 votes
7 votes

Ans- 2. Need Not regular.

Because, Let L= { 0(n)^2 | n >=0},    which is not a regular language. 

           But, L* = 0*,   which is regular.

5 votes
5 votes

$\LARGE L = a^{n!}$ is not Regular 

$\LARGE L^{*} = (a^{n!} )^{*}$ is Regular (n= 0 or 1). It will be  $\LARGE a^{*}$

So, L need not be Regular always.

edited by

Related questions

16 votes
16 votes
2 answers
1
1 votes
1 votes
1 answer
3
go_editor asked May 31, 2016
636 views
Consider a uniprocessor system with four processes having the following arrival and burst times:$$\begin{array}{|c|c|c|l|} \hline&\text{Arrival Time}&\text{CPU Burst Time...