regular expressions and words in the language

Question

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

Answer 1

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.

$(~~(AB)^*~~(C(A^*)~|~B)~~)^*$

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

$\varepsilon,~B,~C,~AB,~CA,~ABB,~ABC,~BAB,~BBB,~BBC,~BCA,~BCB,~BCC,~CAA,~CAB,~CAC,\dots$

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:

$A,~AA,~BA,~AAA,~AAB,~AAC,~ABA,~BAA,\dots$

Answer 2

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.