1. 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  2.

3. 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.  4. hi trowalts;

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!!!  5. 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

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.  6. thanks gandalf...  7. can someone shed some light into this automa thing for me please im new  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   BB code is On Smilies are On [IMG] code is On [VIDEO] code is On HTML code is Off Trackbacks are Off Pingbacks are Off Refbacks are On Terms of Use Agreement