1
$\begingroup$

How to construct regular expression for language L which contain all words in which there is a letter 'a' and the letter 'b'? Of course, I understand that it's easy problem but I just start to learn this science? Please, any advices and hints.

$\endgroup$
  • $\begingroup$ For such problems first you need to define the set of input alphabet or in simpler terms the set of symbols which can appear in your regular expression. $\endgroup$ – Shubham Singh rawat Oct 29 '16 at 15:19
  • $\begingroup$ @ShubhamSinghrawat, for simplicity, let alphabet will be {a, b}. $\endgroup$ – marka_17 Oct 29 '16 at 15:24
1
$\begingroup$

For $ \Sigma = \big\{ a,b \big\} $, all words containing letter $a$ and letter $b$ may be, in my view, expressed as follows: $$ R = (a + b)^*a(a + b)^*b(a + b)^* + (a + b)^*b(a + b)^*a(a + b)^* $$ can be reduced to: $$ R = (a + b)^*\big[ a(a + b)^*b + b(a + b)^*a \big](a + b)^* $$ Graphically: enter image description here
Now: $$\Sigma ^* = \big\{ ab, ba, aab, aaab, babaa, bab, ... \big\}$$
This means any number of letters $a$ and/or $b$ before and after $a$ letter, followed by letter $b$ followed by any number of letters $a$ and/or $b$ or($a$, $b$) in the reverse order, ie. any number of letters $a$ and/or $b$ before and after the letter $b$, followed by a letter $a$ followed by any number of letters $a$ and/or $b$.

$\endgroup$
1
$\begingroup$

Assuming that the input alphabet is $\Sigma = \{a,b\}$, the term $(a|b)^*a(a|b)^*b(a|b)^*$ describes all words where there is an $a$ followed by a $b$, and the term $(a|b)^*b(a|b)^*a(a|b)^*$ describes all words where there is a $b$ followed by an $a$. If we combine both, we get $$ ((a|b)^*a(a|b)^*b(a|b)^*)|((a|b)^*b(a|b)^*a(a|b)^*) $$ which describes the set of all words in which at least one $a$ and one $b$ occurs.

Edit: An even shorter solution would be $$ (a|b)^*(ab|ba)(a|b)^*. $$ However, this solution requires the alphabet to contain exactly $a$ and $b$ whereas the first solution can easily be extended to arbitrary alphabets.

$\endgroup$
  • $\begingroup$ yes, I had similar idea. But now, I need to prove that this regular expression actually describe out language. Could you write little plan how to prove this statement in both directions? $\endgroup$ – marka_17 Oct 29 '16 at 15:33
1
$\begingroup$

If you want to construct regular expression not only for this language that you mentioned also for every other regular language you can simply build NFA, usually building NFA is simple after that you can convert NFA to DFA by power set construction algorithm, in this algorithm you create DFA that all of its states are subset of states in NFA for exmple if statest of NFA are $x_1,\cdots,x_k$ then you have $2^k$ state in DFA and design new transition function such that state $\{q_1,\cdots ,q_n\}$ goes to state $\{p_1, \cdots ,p_m\} $ with $a \in \Sigma$ if from $q_1 , \cdots , q_n$ you can go to $p_1, \cdots, p_n$ with character $a$. after that, you can use an algorithm to convert DFA to RE which is discussed in Micheal Sipser's book.

$\endgroup$
  • 1
    $\begingroup$ You can also convert NFAs to regular expressions directly. $\endgroup$ – Yuval Filmus Oct 29 '16 at 19:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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