# Regular Expression for language [duplicate]

I have a grammer with the following productions,

S -> aA | bC | b
A -> aS | bB
B -> aC | bA | a
C -> aB | bS


I have to construct regular expression for it. I derived words for this language and which are

b, aab, aba, baa, bbb, aaaab, aaaba, aabbb, abaaa, baaaa, ...

So after I deriving the words I concluded that it's a language of strings having odd number of b and having odd length.

It seems to me that you may simply consider the automata with states S, A, B, C and exit state X, and with the following transitions:

S -a-> A
S -b-> C
S -b-> X
A -a-> S
A -b-> B
B -a-> C
B -b-> A
B -a-> X
C -a-> B
C -b-> S


Right?

• Sorry but I'm new to this and I don't know what you're saying here. And also if you could give answer like this: (a+b)* for strings having different combination of a and b Jan 6 '21 at 19:33
• I actually descried a DFA (deterministic finite automaton) that recognizes your language, thus showing that it is indeed possible to write it as a regular expression (this is not true for all languages defined by a grammar). There are methods and tools available online for turning such a DFA into a regular expression. However, I am not sure your regular expression is simple. Jan 6 '21 at 20:17
• For instance, the tools available here ivanzuzak.info/noam/webapps/fsm2regex lead to the following regular expression: (a(bb)*a)*(b+a(bb)*ba)(a(a+b(bb)*ba)+(b+ab(bb)*a)(a(bb)*a)*(b+a(bb)*ba))* Jan 6 '21 at 20:19
• merci! I'll have a look into that. Jan 7 '21 at 10:28

Note that your grammar is regular. Quoting from wikipedia:

A grammar is regular when no rule has more than one nonterminal in its right-hand side, and each of these nonterminals is at the same end of the right-hand side. Every regular grammar corresponds directly to a nondeterministic finite automaton, so we know that this is a regular language.

In theory, every regular grammar generates a regular language. Also, its not hard to construct the relevant NFA for the generated language: for a specific example on how to do that, you can click here (this is actually what has been done in @Matthieu Latapy's answer). Once you have an NFA for the language, you can translate it into a regular expression (there are several ways to achieve this based on state removal methods which are a bit tedious: see here).

BTW, you already know that your language is all words with "odd length and odd number of b's". It is easy to build a DFA for it consisting of 4 states (hint: your language is an intersection of two languages, each having a DFA with two states).

Your language consists of all strings with an even number of $$a$$'s and an odd number of $$b$$'s. How do we construct a regular expression for such a language?

Let us assume for starters that the word starts with $$bb$$. Thus, it has the form $$bba^{n_1}ba^{n_2} \ldots ba^{n_m},$$ where $$m$$ is even and $$n_1+\cdots+n_m$$ is even. This suggests grouping the $$b$$'s in pairs $$ba^kba^\ell$$. There are two types of pairs: a pair with $$k+\ell$$ even, and a pair with $$k+\ell$$ odd. If we denote the first type with $$E$$ and the second type with $$O$$, then our word is of the form $$bs$$, where $$s$$ is a word over $$\{O,E\}$$ with an even number of $$O$$s. Such words $$s$$ are described by the regular expression $$E^*(OE^*OE^*)^*$$. Also, it is easy to express $$E,O$$ as regular expressions: \begin{align} E &= b(aa)^*b(aa)^* + ba(aa)^*ba(aa)^* \\ O &= ba(aa)^*b(aa)^* + b(aa)^*ba(aa)^* \end{align} Altogether, we obtain a regular expression for all words in your language that start with $$bb$$.

In the general case, let the word start with $$a^kba^\ell b$$. If $$k+\ell$$ is even, then this is the same case as before. Otherwise, we need an odd number of $$O$$s, and so the $$\{O,E\}$$ part of the word is described by $$E^*OE^*(OE^*OE^*)^*$$. Altogether, we obtain the following regular expression: $$[(aa)^*b(aa)^*+a(aa)^*ba(aa)^* + a(aa)^*b(aa)^*E^*O + (aa)^*ba(aa)^*E^*O]E^*(OE^*OE^*)^*.$$