Consider the regular expression ((AB)* (C(A*) |B))*

Give three words (over the alphabet {A,B,C}) that are in the language of this expression, and three that are not (and label them accordingly).

Translate the language into an NFA.

I got ABABCAAB, ABABCAAAAB and ABCABABCABABCAB for words that are in the language and :

ABC, ABCCAB and ABCCABBB for words that are not in the language. Am i correct? also not sure which language is being referred to , to translate into an NFA

thank you all , i see where i went wrong

  • $\begingroup$ Stars indicate any number of occurrences, even zero, as I understand. As such, ABC is actually a word in your language. So are the rest of your examples for that matter... For an example of a word that actually is not included in your language, consider BA. $\endgroup$
    – JMoravitz
    Aug 2, 2019 at 13:06
  • $\begingroup$ @Magma Incorrect. Look at the parentheses more closely. The word $B$ is included in the language. $(~~(AB)^*~~(C(A^*)~|~B)~~)^*$. It is zero occurrences of $AB$ followed by the second option of the second term. $\endgroup$
    – JMoravitz
    Aug 2, 2019 at 13:15
  • $\begingroup$ Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to. $\endgroup$ Aug 4, 2019 at 12:08

2 Answers 2


Stars represent any number of occurrences of what precedes, including zero.

In your language, each of your examples of attempts of words which are not included in the language are incorrect.


Since zero occurrences of something with a star is allowed., here are a few more examples of words that are included in your language.


And the list continues.

Now... most of these letters can follow most of the other letters... however there are some catches. If an $A$ appears, it must satisfy one of three conditions, it either immediately precedes a $B$, it immediately follows an $A$, or it immediately follows a $C$.

Examples of words which do not follow this rule:



I'm assuming you understand what the regular expression says.

For "words in the language", start with the simplest (shortest) ones. Clearly, it is a $()^*$, so $\epsilon$ (the empty word) will do.

Next simplest is the outer parenthesis repeated once, then twice, ... In this case, repeated once you can take $\epsilon$ for $(AB)^*$, need to select one of the alternatives for the second part, $C A^*$ (pick $C$ as simplest) or $B$. Can also combine with one or more $AB$, ...

For "words not in the language", you can do the same. I.e., non-empty that do not start $AB$ (like $BA$, just $A$, ...). The expression is several times $A B$ followe by $C$ and $A$s or $B$. It is a bit harder, a way to do it is to come up with some candidate and check it can't be described by the expression.

There are algorithms to translate from a regular expression to a NFA, or you can draw the automaton from your understanding of the expression.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .