Is the regular expression: $(\lambda + a)^*$ equivalent to $a^*$?

1.1k Views Asked by At

I have a question about convert a regular expression to an automaton. In the middle of the regular expression, appears $(\lambda + a)^*$. What I am wondering is: it is not the same of $ a^* $?

If is so, I could simplify the final automaton. $\lambda$ is the symbol for empty string.

1

There are 1 best solutions below

0
On BEST ANSWER

Yes, $(\lambda+a)^*$ and $a^*$ describe the same language.

Depending on which context you meet the task in, you may or may not be expected to follow a particular algorithm mindlessly (construct a NFA from the abstract syntax tree of the regex, convert the NFA to a DFA, minimize the DFA).

Otherwise, you can just write down the trivial (one state, one transition) automaton and be done with it.