Cheap and Secure Web Hosting Provider : See Now

Simple regular expression problem

, , No Comments
Problem Detail: 

new to automata theory and this is quite difficult for me so I'd appreciate a hint in the right direction if possible.

We want to find a regular expression for the language $L$ over $\Sigma = {a,b,c}$ where $L$ is the language of all strings of even length, contain $a$ at least once, and after the final $a$ letter there are no $b$s.

for example - $bcbabaca$ is a valid word.

Best thing I could come up with is somewhat akin to $R = ((a+b+c)(a+b+c))^*a((a+b+c)(a+b+c))^*$ and it has to be something like that since we need to control the length of the word to make it even, but still its no good and im having difficulties.

Asked By : Oria Gruber
Answered By : David Richerby

You're almost there.

$((a+b+c)(a+b+c))^∗$ gives you strings of even length.

$((a+b+c)(a+b+c))^∗a$ gives you strings of even length plus an $a$. That is, odd-length strings that contain at least one $a$ and end with an $a$.

Now, we're told that there are no $b$s after the last $a$. And there are certainly no $a$s after the last $a$, because that's what "last" means! So there can only be $c$s after the last $a$.

So, the answer is going to have to look something like $((a+b+c)(a+b+c))^∗ac^*$. That's not quite right, because it doesn't force the whole string to be even-length and it does force the last $a$ to be in an odd-numbered position in the string (whereas, hint, it should be able to be even or odd).

I'm going to stop there because you showed enough in the question that I think you can finish this yourself, now.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/59747

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback