I want to translate the following grammar into a regular expression:
Set of variables
V := {S,T}
Set of terminals
Σ := {a,b}
Set of relations
S → ""
S → aS
S → bT
T → aT
T → bS
Start variable
S
For the regular expression I can only use the following operations:
concatenation, union and star (no difference)
and I can use the empty word and sigma (set of all words in the alphabet).
I do know how to "formulate" the expression in words... but I have problems to express it in a regular expression.
HINTS:
Look at the grammar, find some stuff that you can produce, find some stuff that you can't produce. For instance, I can produce the strings $a, aa, aaa, aaaa, ...$. I can also produce the strings $bb, bab, baab, ...$. I cannot produce the strings $ab, aba, abaa, abaaa...$
Now, this is written in a way that makes it really easy to convert it into a DFA. Our two states can be labelled $S$ and $T$, and the transitions are (hopefully) fairly obvious. Look at the DFA and try and express as simply as possible what it will and will not accept before turning it into a regular expression. From there, just use the tools you have available.
SPOILERS:
The grammar can be represented by a DFA with state space $\{S,T\}$, accepting state $S$ and starting state $S$. On reading an $a$ we remain in our current state. On reading a $b$, we flip to the other state. The recognised language is the set of all strings containing an even number of $b$s.
The regular expression $a^*ba^*ba^*$ will recognise all strings with exactly two $b$s. The regex $(a^*ba^*ba^*)^*$ will recognise all words where the number of $b$s is a positive multiple of $2$. We can either unite or prepend this regex with $a^*$ to get the language of all words with an even number of $b$s.