How to read formal definition of a language.

Question

I need to give nondeterministic finite automata for the following language: $$ L = \{w \in \{a, b\}^∗ \mid w \in ba^*a \cup ((a \cup bb)^*ab^*)\} $$ The * above are Kleene Stars

I'm having trouble reading this, I think its:

Language $L$ is a set of strings, such that each string $w$ is of the form: Zero or more $ba$, then $a$, then zero or more $abb$, then zero or more $ab$.

Is this right, if not where have I gone wrong?

Thanks.

You haven't put in enough parentheses for an unambiguous reading. Do you really mean $ba^$, or do you mean $(ba)^$? They are two different things. The first includes $baa$ but not $baba$, the second, the opposite. — Gerry Myerson, Mar 25 '19 at 03:52
In that case, I think it must mean ${,b,ba,baa,baaa,\dots,}$. — Gerry Myerson, Mar 25 '19 at 08:33

score 1 · Accepted Answer · answered Mar 25 '19 at 03:55

1

You seem to be ignoring the $\cup$s, which I gather means "or". Plus, I think you're interpreting the $^*$s incorrectly.

If $w \in L$, then $w$ may be of the form $ba^*a$, or it may be of the form $(a \cup bb)^*ab^*$. The former is $b$ followed by one or more $a$s. Otherwise, it is zero or more instances of $a$ or $bb$ repeated (e.g. $aaabbabbbbbba$), followed by another $a$, then by zero or more $b$s.

answered Mar 25 '19 at 03:55

Theo Bendit

50,900

My understanding of the * was its the set of all strings of a given set, combined and concatenated in any order. So with set K = {cat, dog}, then K* = { Ɛ, cat, dog, catcat, catdog, dogdog, catcatcat, catcatdog, etc }. And the ∪ is the union of the sets, so (a ∪ bb )* would be any combination of the set {a, bb}? EG { Ɛ, a, bb, abb, abbbb, aabb, etc }. Is that wrong? – Adrian M Mar 25 '19 at 06:00
Yes, any combination of $a$ and $bb$, but not necessarily with all the $a$ preceding all the $b$, e.g., $bba$ is in it, as well as $bbaaabbbbabb$ and so on. – Gerry Myerson Mar 25 '19 at 08:35

How to read formal definition of a language.

1 Answers1