Results 1 to 3 of 3

Math Help - Automata Proof... Theory of Computation

  1. #1
    Super Member Aryth's Avatar
    Joined
    Feb 2007
    From
    USA
    Posts
    652
    Thanks
    2
    Awards
    1

    Automata Proof... Theory of Computation

    Theorem

    The class of regular languages is closed under the union operation.

    (In other words, if A_1 and A_2 are regular languages, so is A_1 \cup A_2.)

    Problem

    Prove this theorem using the Proof by Construction method.

    Useful Information

    A regular language merely means that some finite automaton M recognizes A.

    Definition of A \cup B:

    A \cup B = \{ x|x\in A \vee x\in B\}

    So:

    We have A_1 which is recognized by the finite automaton M_1 and we have A_2 which is recognized by the finite automaton M_2.

    Definition of a finite automaton (Deterministic):

    M = (Q, \Sigma , \delta , q_0, F) where:

    Q = \text{Finite set called the States}

    Meaning:

    Q = \{ q_0, q_1, q_2, ..., q_n\},

    \Sigma = \text{Finite set called the Alphabet}

    It's all possible symbols that can be used as an input, for example, binary is:

    \Sigma = \{ 0, 1\}

    \delta = \text{The transition function}

    \delta : Q \ x \ \Sigma \longrightarrow Q

    q_0 = \text{The Start State}

    F = \text{Set of Accept States}

    Meaning that this set only contains the states from Q that the computation accepts. They are usually recognizable.

    Proof

    Here's what I've gotten so far:

    Let M_1 recognize A_1, where M_1 = (Q_1, \Sigma , {\delta}_1, q_1, F_1), and
    M_1 recognize A_2, where M_2 = (Q_2, \Sigma , {\delta}_2, q_2, F_2).

    Now, I have to construct an M to recognize A_1 \cup A_2, where M = (Q, \Sigma , \delta , q_0, F).

    I know the first step, and that's to define Q:

    1. Q = \{ (r_1, r_2)|r_1\in Q_1 \ \wedge \ r_2\in Q_2\}.

    The Second Step is to define the language:

    2. We will assume that the language is the same for both automata. If the case may be that they have separate languages, then the language for M will be:

     \Sigma = {\Sigma}_1 \cup {\Sigma}_2

    From here I have no idea what to do... Anyone know how to do this?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Dec 2007
    Posts
    131
    I am in a class where we learned this, but my teacher didnt make us prove these properties formally. What we did was show that if we have two NFAs M_1 and M_2 which recognize the languages A_1 and A_2, respectively, then we can create a new machine M_{1 \cup 2} which recognizes A_1 \cup A_2 by creating a new start state with an \epsilon transition to the start states of M_1 and M_2. This way, the new machine will nondeterministically recognize A_1 or A_2. Then, since we have constructed an NFA which recognizes the language M_{1 \cup 2}, it must be regular, since NFAs are equivalent to regular expressions. I will go through my book to see how you formalize the argument. Sorry if this doesn't help.

    edit: OK, so your next step should be to create a new start state q_0 and describe your new transition function \delta=\{ \delta_0 , \delta_1 , \delta_2 \} with \delta_0 \left( {q_0 , \epsilon} \right) = \{ q_1 ,q_2 \}<br />
and keep \delta_1 and \delta_2 the same. Then you make F=\{ F_1 \cup F_2 \}. You should also make Q=\{q_0 , Q_1, Q_2 \}. Hope this is correct and helps.

    edit 2: I just saw you are working deterministically, so if you haven't learned about NFAs then this is kind of a useless post.
    Last edited by xifentoozlerix; April 12th 2008 at 03:21 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Aryth's Avatar
    Joined
    Feb 2007
    From
    USA
    Posts
    652
    Thanks
    2
    Awards
    1
    I know about NFAs and such, but this is a purely Deterministic Automaton and should be constructed strictly as a Deterministic Automaton.

    But thanks, there's some useful information in there.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Automata
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: July 6th 2010, 08:20 AM
  2. Regular Expression (Theory of Automata)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 10th 2010, 05:58 AM
  3. Radon Nikodym computation, step of a proof
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: March 5th 2010, 11:09 AM
  4. Help in Theory of Automata
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 10th 2009, 06:04 AM
  5. Problems relating Theory of Automata (Computer Theory)
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: October 17th 2007, 10:52 AM

Search Tags


/mathhelpforum @mathhelpforum