0
$\begingroup$

If there is a transition with no input in the FA, when it is converted to a regular expression should it be accepted as ɛ transition? As an example picture shown below, should regular expression showing possible transitions between 1 and 3 (1-2-3 , 1-3) be accepted (ab+ɛ) or just ab?enter image description here

$\endgroup$
1
$\begingroup$

The regular expression is supposed to match (exactly) all of the words that the automaton accepts. If you pretend that some of the transitions of the automaton don't exist, you're effectively converting a different automaton, and that automaton probably accepts different strings from the ones you're supposed to accept.

In this specific case, pretending that there's no $\varepsilon$-transition from the first state to the third one means that the automaton no longer accepts the word $c$.

$\endgroup$
0
$\begingroup$

Any epsilon transition from a start state to state $x$ would mean $x$ is also a start state because you can get to state $x$ with no input (via epsilon transitions). In your image, states 1 and 3 would thus both be valid starting states and you could start accepting input from either. So yes, with no input, not only can you be at state 3, but you are at state 3. A regular expression representing your FA could be something like /(ab)?c/. We can optionally have ab, because we start at states 1 and 3, but then we are required to have c.

One thing to note, because your FA can be in multiple states at once (e.g. it can be at 1 and 3 before it starts accepting) it is a non-deterministic finite automata. You can get around this by converting it to a deterministic finite automata. A pretty common algorithm for this is the powerset construction. Then you can minimize it if you'd like using DFA minimization algorithms.

$\endgroup$
0
$\begingroup$

We can read the equations of your machine from the diagram: $$\begin{align} S_1 & = a S_2 + S_3 \\ S_2 & = b S_3 \\ S_3 & = c S_4 \\ S_4 & = \epsilon \end{align}$$

The equation for $S_1$ has an epsilon transition to $S_3$.

We can solve for $S_1$ bottom up: $$\begin{align} S_3 & = c \\ S_2 & = b c \\ S_1 & = a b c + c \\ \end{align}$$


It is always possible to eliminate the other states one by one to get a regular expression for the entry state. Since the equations are right linear, they can be put in the form

$$\mathsf V = \mathcal R + \mathcal S \; \mathsf V$$

where

  • $\mathsf V$ is a non-terminal and
  • $\mathcal R$ and $\mathcal S$ are regular expressions free of $\mathsf V$.

The solution to the equation is $$\mathsf V = \mathcal S^* \mathcal R$$

Note that the right-hand side is free of $\mathsf V$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.