Results 1 to 3 of 3

Thread: Automata Proof... Theory of Computation

  1. #1
    Super Member Aryth's Avatar
    Joined
    Feb 2007
    From
    USA
    Posts
    666
    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 $\displaystyle A_1$ and $\displaystyle A_2$ are regular languages, so is $\displaystyle 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 $\displaystyle A \cup B$:

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

    So:

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

    Definition of a finite automaton (Deterministic):

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

    $\displaystyle Q = \text{Finite set called the States}$

    Meaning:

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

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

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

    $\displaystyle \Sigma = \{ 0, 1\}$

    $\displaystyle \delta = \text{The transition function}$

    $\displaystyle \delta : Q \ x \ \Sigma \longrightarrow Q$

    $\displaystyle q_0 = \text{The Start State}$

    $\displaystyle F = \text{Set of Accept States}$

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

    Proof

    Here's what I've gotten so far:

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

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

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

    1. $\displaystyle 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 $\displaystyle M$ will be:

    $\displaystyle \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 $\displaystyle M_1$ and $\displaystyle M_2$ which recognize the languages $\displaystyle A_1$ and $\displaystyle A_2$, respectively, then we can create a new machine $\displaystyle M_{1 \cup 2}$ which recognizes $\displaystyle A_1 \cup A_2$ by creating a new start state with an $\displaystyle \epsilon$ transition to the start states of $\displaystyle M_1$ and $\displaystyle M_2$. This way, the new machine will nondeterministically recognize $\displaystyle A_1$ or $\displaystyle A_2$. Then, since we have constructed an NFA which recognizes the language $\displaystyle 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 $\displaystyle q_0$ and describe your new transition function $\displaystyle \delta=\{ \delta_0 , \delta_1 , \delta_2 \}$ with $\displaystyle \delta_0 \left( {q_0 , \epsilon} \right) = \{ q_1 ,q_2 \}
    $ and keep $\displaystyle \delta_1$ and $\displaystyle \delta_2$ the same. Then you make $\displaystyle F=\{ F_1 \cup F_2 \}$. You should also make $\displaystyle 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; Apr 12th 2008 at 02:21 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Aryth's Avatar
    Joined
    Feb 2007
    From
    USA
    Posts
    666
    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: Jul 6th 2010, 07:20 AM
  2. Regular Expression (Theory of Automata)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 10th 2010, 04:58 AM
  3. Radon Nikodym computation, step of a proof
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: Mar 5th 2010, 10:09 AM
  4. Help in Theory of Automata
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Dec 10th 2009, 05:04 AM
  5. Problems relating Theory of Automata (Computer Theory)
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: Oct 17th 2007, 09:52 AM

Search Tags


/mathhelpforum @mathhelpforum