1
$\begingroup$

I know how to find a regular expression when given a FA. But how do I find a regular expression given just a language and its rules?

For example, for the language $L \subset \{ a,b\}^* $ which accepts all words that contain exactly one $aa$. How do I find a regular expression in this case?

I know that I would be able to FA and convert it into a regular expression, but this can be time-consuming. Is there a faster/easier way that I could use in an exam to save time?

$\endgroup$
1
$\begingroup$

I'm not aware of any general methods, and personally I'm not interested in tricks which are only useful in exams. However, I can explain how to find an expression for your particular example. The way to get better with this kind of exercise is to solve a few of them.

A word which contains exactly one $aa$ has the form $xaay$, where $x,y$ contain no $aa$, $x$ doesn't end with $a$, and $y$ doesn't start with $a$. This suggests first determining how to write a regular expression for the set of words avoiding $aa$.

If a word avoids $aa$, then any two occurrences of $a$ are separated by $b^+$. We can describe all such words by the following infinite regular expression: $$b^* + b^*ab^* + b^*ab^+ab^* + b^*ab^+ab^+ab^* + \cdots.$$ This can be represented by the finite regular expression $b^* + b^*(ab^+)^*ab^*$.

For the sake of our original problem, we need to impose the further constraint that the word not end with $a$. We obtain the following infinite regular expression for the set of all words avoiding $aa$ and not ending with $a$: $$ b^* + b^*ab^+ + b^*ab^+ab^+ + \cdots = b^*(ab^+)^*. $$ Similarly, a regular expression for the set of all words avoiding $aa$ and not starting with $a$ is $(b^+a)^*b^*$.

Putting everything together, a regular expression for the set of all words containing exactly one copy of $aa$ is $$ b^*(ab^+)^*aa(b^+a)^*b^*. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy