1
$\begingroup$

Good day,
I was given the below question that relates to Kleene's Theorem (RE to FA):

Question
Consider the following FA's with the corresponding regular expressions $r_1$ and $r_2$

$r_1$:
image of r1

$r_2$:
image of r2

Build an FA for the regular expression $r_1r_2$ by applying Kleene's theorem (do not formulate any regular expression)

Note: I only need to create a table with the z states. I know how to do this but I get stuck when the new z state is a starting state in one FA but not in the other one. Let me give you an example:

table for new z states r1r2

Is z3 also a starting state (-z3), because it circles back to itself, in $r_1$, if the input in -z1 is a b or not? Is there only one starting state in the new FA for $r_1r_2$?

This is the only thing I get stuck on. I need to know this if I want to finish the table and draw the new FA for $r_1r_2$.

Thank you.

$\endgroup$
11
  • $\begingroup$ Can you clarify: 1. What does + and - mean? Accepting/final state and starting/initial state? 2. When you ask for $r_1r_2$, do you mean $\left\{xy\mid x\in r_1,y\in r_2\right\}$ (concatenation) or $r_1\cup r_2$ (alternation)? 3. Is this a DFA or NFA, and are you allowed to output a NFA? $\endgroup$ Commented May 27, 2020 at 23:12
  • $\begingroup$ 1. + denotes starting state and - denotes final state. 2. The new (3rd) FA will accepts the language defined by the regular expression $(r_1 + r_2)$. 3. DFA and I no I'm not allowed to output NFA. $\endgroup$ Commented May 27, 2020 at 23:44
  • $\begingroup$ Isn't this backwards? You now have 3 starting states and 1 final state on $r_2$ $\endgroup$ Commented May 27, 2020 at 23:48
  • $\begingroup$ Question. In my table, if I input a b in the starting state $z_1$ then it goes to the new state $z_3$ which is $x_1$ or $y_1$. Is $z_3$ a new starting state or neither starting nor final? $\endgroup$ Commented May 27, 2020 at 23:53
  • $\begingroup$ Edited answer: 1. never a starting state 2. final as long as either $r_1$ accepts or $r_2$ accepts $\endgroup$ Commented May 27, 2020 at 23:54

1 Answer 1

Reset to default
1
$\begingroup$

I am going to presume the following interpretations:

  1. $+$ denotes an accepting state (end here, the string is accepted)
  2. $-$ denotes the unique starting state (you start here)
  3. $r_1r_2$ asks for the alternation of the regular expressions, typically denoted $r_1|r_2$

For the specific special case of two DFA inputs to $r_1|r_2$, you can simulate both paths at once in parallel.

  1. Keep track of all found possibilities of states (X,Y) where X is a state of $r_1$ and Y is a state of $r_2$
  2. The only initial state is (initial state of $r_1$, initial state of $r_2$)
  3. Whenever you are in state (X,Y) seeing input letter $z$, go to (wherever X goes to on input $z$, wherever Y goes to on input $z$).
  4. All states (X,Y) such that either X accepts in $r_1$ or Y accepts in $r_2$ will accept for $r_1|r_2$.

These general constructions work for any input, including NFAs:

To construct the concatenation $r_1r_2$, that is $\left\{xy\mid x\in r_1,y\in r_2\right\}$, simply do the following:

  1. Repeat the entire DFA (or NFA, it doesn't matter) representation of both $r_1$ and $r_2$ as states and transitions.
  2. Only the initial (-) state(s) of $r_1$ are initial states of $r_1r_2$.
  3. Only the final (+) state(s) of $r_2$ are final states of $r_1r_2$.
  4. Add $\epsilon$-transitions (those that consume zero input) connecting each final state of $r_1$ to each initial state of $r_2$.
  5. Convert the NFA to DFA if necessary.

To construct the alternation $r_1|r_2$, that is $r_1\cup r_2$, simply do the following:

  1. Repeat the entire DFA/NFA representation of both $r_1$ and $r_2$ as states and transitions.
  2. All initial (-) and final (+) states of $r_1$ and $r_2 $ are simply initial/final states of $r_1|r_2$.
  3. If you need a unique start state, create one, and add $\epsilon$-transitions connecting the start state to each initial state of both $r_1$ and $r_2$.
  4. Convert the NFA to DFA if necessary.

You can consider all transitions that lead to state X to be copied (keeping the original) to lead to wherever X goes to under $\epsilon$-transitions.

Nothing will avoid having multiple transitions - this is, after all, a real use of nondeterminism. The $\epsilon$-transitions represent "guessing", either where the end of the first substring part is (for $r_1r_2$) or which type of string to match to begin with (for $r_1|r_2$).

The NFA$\rightarrow$DFA conversion of course can lead to exponential blowup (the new set of states is the powerset, i.e. set of all subsets, of the original states). Typically the number of reachable subset-states is very limited.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.