Notices
Results 1 to 6 of 6

Thread: Automata

  1. #1 Automata 
    Forum Freshman
    Join Date
    May 2009
    Posts
    6
    I really need help with my automata subject... Please if anyone knows how to write the regular languages of this problem..
    the alphabet here is {a,b}

    1. regular expression for w contains even number of a's and b's
    2. every a is followed by b
    3. palindrome: w = reverse of w

    -----------thanks in advance


    Reply With Quote  
     

  2.  
     

  3. #2 Automata... 
    New Member
    Join Date
    Jul 2009
    Posts
    1
    Hi analynsarte, I really enjoyed automata although its been a while so I might be a bit rusty.

    Firstly number 1 and 3 cant be solved,
    "regular expression for w contains even number of a's and b's" that means that any of the following expressions are valid, "ababa", "aaabbb" (those are easy to write a regular expression for, but then you find things like this which are also valid, "aababbb" and "bbbababaabaa", the thing is you cant write a regular expression that will except ANY word (of any length) if that word does not follow a pattern.

    Number 2. "every a is followed by b", could be done like so:
    (ab)*|b* since we dont give a damn about the b's which can run wild, as long as there is a 'b' after an 'a' its all good.

    And lastly the 3rd, "palindrome: w = reverse of w" is not possible, it is for a fixed length, where the word is not bigger than some predetermined length, but even then it will be a complicated expression.

    If you get confused think how you would draw the state diagram, all regular expressions can be expressed as a finite state machine, if you cant draw the fsm then it cant be expressed as a regular expression.


    Reply With Quote  
     

  4. #3  
    Forum Freshman
    Join Date
    May 2009
    Posts
    6
    hi trowalts;

    thanks for the reply,...

    for problem 1, what i mean is- it is mandatory that both the cardinality of a and b is even, so the following expression is valid:{e,aabb,abab,abba,bbaa,...} and ababa is not...

    do you know any references about automata? thanks again!!!

    looking forward with your reply...
    Reply With Quote  
     

  5. #4 Re: Automata 
    Forum Freshman
    Join Date
    May 2009
    Posts
    5
    Quote Originally Posted by analynsarte
    I really need help with my automata subject... Please if anyone knows how to write the regular languages of this problem..
    the alphabet here is {a,b}

    1. regular expression for w contains even number of a's and b's
    2. every a is followed by b
    3. palindrome: w = reverse of w

    -----------thanks in advance
    I studied these things many years ago, so I might be wrong. Usually we prove that a language is not regular by using the Pumping Lemma (PL). But that's not very pleasant. Instead of looking at regular expressions, let's look at finite automata. A finite automaton has a finite number of states, and states is all you have in order to keep track of what you've done so far and, therefore, of what need to be done.

    1. regular expression for w contains even number of a's and b's
    This is a regular expression because we never need more than 2 bits to remember where we are:
    00 = we are OK
    01 = we need another 'b'
    10 = we need another 'a'
    11 = we need another 'a' and another 'b'

    Thus, we need 4 states:
    OK ----a----> NEEDA
    OK ----b----> NEEDB
    NEEDA----a---->OK
    NEEDA----b---->NEEDA&B
    NEEDB----a---->NEEDA&B
    NEEDB----b---->OK
    NEEDA&B----a--->NEEDB
    NEEDA&B----b--->NEEDA

    This is tough:
    ( aa | bb | (ab|ba)(aa+bb)*(ab+ba) )*

    2. every a is followed by b
    This is simple: we just need one bit:
    0 = we don't need a 'b'
    1 = we need a 'b' right now

    We have 2 states:
    OK ----a---->NEEDB_NOW_
    OK ----b---->OK
    NEEDB_NOW_----b---->OK

    (ab|b)*

    3. palindrome: w = reverse of w
    Impossible. If a string is palindrome and of length n, we need to remember n/2 characters to check that it is really palindrome. That n is unbounded, because if we fix a number of states, then we can enter a string that would need even more states. Remember that states =~ MEMORY.
    Reply With Quote  
     

  6. #5  
    Forum Freshman
    Join Date
    May 2009
    Posts
    6
    thanks gandalf...
    Reply With Quote  
     

  7. #6 im new 
    Forum Freshman
    Join Date
    Sep 2009
    Posts
    19
    can someone shed some light into this automa thing for me please im new
    BANKAI........
    Reply With Quote  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •