7
$\begingroup$

I'm constructing a deterministic finite automata (DFA) for a language of all strings defined over $\{0,1\}$ whose length is even and number of $1$s is odd. I constructed each DFA separately and then combined:

dfas and their union

  • Is the given procedure for combining DFAs correct?
    EDIT: Originally wrote union; actually taking the intersection.
  • Would someone suggest material on constructing DFAs
    given restrictions on length and number of $0$s or $1$s?

According to link given by Merbs, I have developed this FA. enter image description here
This FA does not accept a language of even length.

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ Your approach seems correct, but you should use the intersection and not the union of the two DFAs. $\endgroup$
    – A.Schulz
    Commented Nov 25, 2012 at 19:10
  • $\begingroup$ I have learnt only 3 methods like union of FAs, concatenation of FAs and closure of FA. I am searching but cant find the intersection of FAs. Can you point me to some useful link? $\endgroup$
    – Rafay Zia Mir
    Commented Nov 25, 2012 at 19:44
  • 1
    $\begingroup$ From a Google search: this site is good, but the gist is that you take the intersection of the accepting states. $\endgroup$
    – Merbs
    Commented Nov 25, 2012 at 21:36
  • $\begingroup$ i have visited this link but this provides a specific example not a rule, bcz when we come across some difficult FA then it would be difficult to construct intersection. $\endgroup$
    – Rafay Zia Mir
    Commented Nov 26, 2012 at 16:22
  • $\begingroup$ Given two DFAs with $m$ and $n$ states, constructing a DFA with $mn$ states (with each state representing a pair of states in the original DFAs) is the rule; and then you can minimize the resulting DFA through a set of (mostly heuristic?) procedures. $\endgroup$
    – Merbs
    Commented Nov 27, 2012 at 7:48

2 Answers 2

Reset to default
8
$\begingroup$

Yes, this is called the Product Constuction - given DFAs $M_1$ and $M_2$, we can construct $M=M_1\times M_2$:

  • $M$ consists of pairs of states from its constituent DFAs, so if the original DFAs have states $A,B,C$ and $x,y,z$, the product would be $\{Ax,Ay,Az,Bx,By,Bz,Cx,Cy,Cz\}$.
  • The transition function is updated such that if on a particular step, a string would cause $M_1$ to transition from state $A$ to $B$ and $M_2$ to transition from $x$ to $y$, then the product would transition from $Ax$ to $By$
  • The initial state is the pair consisting of the initial states of the constituent DFAs (i.e. $Ax$).
  • If we are constructing the DFA that determines whether both of the two constituent DFAs would accept the string, then the accept states of $M$ is the intersection (those pairs made up of accept states from both).
    If we are constructing the DFA that determines whether either of the two constituent DFAs would accept the string, then the accept states of $M$ is the union (those pairs made up of accept states from either).
    In your example, $x_1$ and $y_0$ are the accept states of $M_1$ and $M_2$; the intersection would be $\{x_1y_0\}$ while the union would be $\{x_1y_0,x_1y_1,x_0y_0\}$.

I’ve included some other DFAs regarding restrictions on length for reference.

example dfas

Improve this answer
$\endgroup$
3
  • $\begingroup$ In cases of union, should the set of accepting states not be $M_1Q_2 \cup Q_1M_2$? (Not that anyone would use this construction for union; in that cases, $|Q_1|+|Q_2|+1$ states suffice as opposed to $|Q_1||Q_2|$ this construction yields. At least if we are talking NFA.) $\endgroup$
    – Raphael
    Commented Dec 3, 2012 at 21:41
  • $\begingroup$ @Raphael, your comment, while correct, was complicated enough that I didn't understand it without further thought, so I attempted to "laymenize" it. If you'd like to edit my answer to include a discussion on NFAs, you can make it a community wiki (or add your own answer). $\endgroup$
    – Merbs
    Commented Dec 4, 2012 at 4:13
  • $\begingroup$ @Merbs, thanks for your help and answer. Sorry for late reply but i tried this method to other FA`s and this was successful. $\endgroup$
    – Rafay Zia Mir
    Commented Dec 9, 2012 at 17:35
1
$\begingroup$

OK, "laymanized" a bit. Take DFAs $M_1 = (Q_1, \Sigma, \delta_1, q_1, F_1)$ and $M_2 = (Q_2, \Sigma, \delta_2, q_2, F_2)$. Consider the DFA $M = (Q_1 \times Q_2, \Sigma, \delta, (q_1, q_2), F_1 \times F_2)$, where $\delta$ is defined by: $$ \delta((q', q''), a) = (\delta_1(q', a), \delta_2(q'', a)) $$ The idea is that the state of $M$ records the states in which $M_1$ and $M_2$ would be if they processed the string separately. $M$ accepts only if both of them do.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Not sure in which way this is "laymanized"; this is the (correct) formal definition for the product construction. You should mention how the state set of $M$ can be reduced in many cases; nobody wants to draw all that crap. $\endgroup$
    – Raphael
    Commented Jan 18, 2013 at 15:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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