Results 1 to 2 of 2

Math Help - Using Kleene's Theorem for Finite Automata State Elimination

  1. #1
    Newbie
    Joined
    Sep 2011
    Posts
    17

    Using Kleene's Theorem for Finite Automata State Elimination

    When using Kleene's Theorem in order to determine the regular expression represented by a finite automata, are you able to simply immediately eliminate the dead states since they wouldn't be part of the regular expression? If not, how would they factor into the regular expression?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773

    Re: Using Kleene's Theorem for Finite Automata State Elimination

    By Kleene's theorem, do you mean the regular theorem about converting finite automata into regular expressions? The one with

    R(i,j,k)=R(i,j,k-1)\cup R(i,k,k-1)R(k,k,k-1)^*R(k,j,k-1)

    where R(i,j,k) is the regular expression for words that go from state i to state j through states no higher than k?

    "Are you able" is a little vague. The theorem contains an algorithm that works for all states, dead or not. If you want, you can perform simplifications along the way. If you know that k is a dead state, then R(i,k,k-1) is empty when i\ne k, and so R(i,j,k)=R(i,j,k-1) for all i\ne k and j. On the other hand, in the middle of the algorithm, it may not be clear which states are dead (they may be accessible through states with higher numbers).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Kleene Normal Form Theorem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 11th 2012, 09:01 AM
  2. Finite Automata limitations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 6th 2010, 09:57 AM
  3. Finite Automata question
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: July 7th 2009, 02:33 PM
  4. Finite Automata Question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 25th 2008, 08:52 AM
  5. Questions relating to Sigma & Finite Automata
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 3rd 2008, 10:21 AM

Search Tags


/mathhelpforum @mathhelpforum