Results 1 to 3 of 3

Math Help - Finite Automata limitations

  1. #1
    Newbie
    Joined
    Dec 2010
    Posts
    6

    [SOLVED]Finite Automata limitations

    I am trying to clear something that seems to be a little misleading for me.

    I know the language over {a,b} consisting of all words containing the same number of occurrences of
    the symbol a as of the symbol b is not regular.

    I know that the language L over {a,b} consisting of all words containing
    the same number of occurrences of ab as a substring as occurrences of ba as a substring
    actually is regular.

    What would be the best way to prove the sub string language??
    by finding a finite automaton that accepts this language? or have i got the wrong idea?

    Hope someone can point me in the right direction.
    Last edited by tom9999; December 6th 2010 at 10:14 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,418
    Thanks
    718
    Yes, this seems surprising at first. The difference here is that recognizing the first language requires unlimited memory. Indeed, to check whether a^nb^n is in the language, the automaton has to read all a's and remember their number, then read all b's and check that their number is the same as that of a's.

    Recognizing the second language, on the other hand, does not require infinite memory because one cannot have a sequence of "ab" without also having "ba". Note that it is crucial that the alphabet does not contain other symbols besides a and b. Suppose there is a substring "ab". To have another "ab" further along, one must first encounter "ba". Therefore a counter that contains the number of "ab" minus the number of "ba" encountered so far cannot go above 1 or below -1. A finite automaton can track this and accept a word if the counter is 0 at the end.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2010
    Posts
    6
    Thanks very much i have now made a automata that accepts it so i know its regular.

    Thanks for your help
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: September 26th 2011, 11:53 AM
  2. Limitations!
    Posted in the Calculus Forum
    Replies: 3
    Last Post: March 1st 2010, 09:55 PM
  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