1,576 views

1 Answer

Best answer
10 10 votes
$\phi = \{\}$, which is empty set. Now by definition of *, it repeats the content of a set ZERO or more times. And anything repeated zero time is $\epsilon$. And nothing repeated 1 or more times is nothing.

So, $\phi^*$ generates  the language $\{\epsilon\}$ whose regular expression is $\epsilon$. Hence,
$$\phi^* = \epsilon$$

It can be also shown as:

$a^* \text{ generates } \{\epsilon, a, aa, aaa, ....\}$
$\phi^* \text{ generates } \{\epsilon\}$
• selected by
Position:
Show:

Related questions

51 51 votes
6 answers 6 answers
13.7k
13.7k views
Misbah Ghaya asked Nov 29, 2016
13,682 views
How many substrings (of all lengths inclusive) can be formed from a character string of length $n$? Assume all characters to be distinct, prove your answer.
0 0 votes
0 0 answers
569
569 views
admin asked Oct 17, 2019
569 views
Let $PREFIX-FREE_{REX} = \{\langle R \rangle \mid \text{R is a regular expression and L(R) is prefix-free}\}$. Show that $PREFIX FREE_{REX}$ is decidable. Why does a simi...
0 0 votes
0 0 answers
701
701 views
admin asked Oct 15, 2019
701 views
Consider the problem of determining whether a DFA and a regular expression are equivalent. Express this problem as a language and show that it is decidable.
1 1 vote
3 answers 3 answers
591
591 views
ASHIS 1 asked Apr 28, 2025
591 views
State Proof of Correctness for Different Popular Sorting AlgorithmSorting AlgoBest Case TCAVg Case TCWorst Case TCStable Sorting?Inplace Sorting?1. Bubble Sort \[O(n) \]\...