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.

Can you please help me to construct regular expression for it.

I appreciate your help.


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

DFA for your language


  • $\begingroup$ 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 $\endgroup$ Jan 6 at 19:33
  • $\begingroup$ 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. $\endgroup$ Jan 6 at 20:17
  • $\begingroup$ 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))* $\endgroup$ Jan 6 at 20:19
  • $\begingroup$ merci! I'll have a look into that. $\endgroup$ Jan 7 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^*)^*. $$


Not the answer you're looking for? Browse other questions tagged or ask your own question.