2
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ What words did you produce? $\endgroup$
    – shade4159
    Nov 4, 2013 at 17:39
  • $\begingroup$ In the specified language of the grammar I can produce words like a , aba, abab and so on. It is important that after the first b occurs, an a or b has to follow. $\endgroup$
    – Georges
    Nov 4, 2013 at 17:43
  • $\begingroup$ More importantly, what words can't be produced? $\endgroup$ Nov 4, 2013 at 17:45
  • $\begingroup$ You say you know how to formulate the expression in words. What formulation have you deduced? $\endgroup$
    – ymbirtt
    Nov 4, 2013 at 17:48
  • $\begingroup$ @ymbirtt a word which starts empty or with any number of a, followed by nothing or a b, than an a or b has to follow, if an a follows it can repeat it self, if a b follows than it can start all over again. $\endgroup$
    – Georges
    Nov 4, 2013 at 17:57

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you for the great hint with the DFA. I did not recognize the pattern...uff $\endgroup$
    – Georges
    Nov 4, 2013 at 18:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .