Regular expression that represents the words s.t. start with $a$ and have an odd quantity of $a$'s

38 Views Asked by At

Find a regular expression that represents the language "The words over the alphabet $\{a,b,c\}$ such that end with a pair of letters, or start with $a$ and have in total an odd quantity of $a$'s".


The null word is represented by $\varepsilon$.

I know how to represent the first part: $$(a+b+c)^*(a+b+c)^2.$$ For example, the word $abbb\in L$ because it ends with $bb$, and the RE $(a+b+c)^*(a+b+c)^2$ accepts it.

But I am not able to complete the other part of the statement: the incomplete regular expression is $$(a+b+c)^*(a+b+c)^2+\text{???}.$$ I know that if one wants to represent odd $a$'s then the RE is $a(aa)^*$, but here the order matters.

If I say $$a(a+b+c)^*a(\varepsilon+b+c)^*(aa)^*(b+c)^*$$ then the word $abaaaa\in L$ but $ababa$ is not in the language.

Some other words that are in the language: $aaa$, $aabcabaa$, $abc$, $abbbcaabaacaaaa$.

Thanks!!

1

There are 1 best solutions below

1
On BEST ANSWER

The answer is:

$a((b+c)^*a(b+c)^*a(b+c)^*)^*$.