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

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. — JMoravitz, Aug 02 '19 at 13:06
@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. — JMoravitz, Aug 02 '19 at 13:15
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. — José Carlos Santos, Aug 04 '19 at 12:08

score 1 · Answer 1 · answered Aug 02 '19 at 13:25

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$

vonbrand · Answer 2 · 2019-08-02T13:57:17.403

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.

regular expressions and words in the language

2 Answers2