[Math] Regular expressions represents the sets provided

formal-languagesregular expressionsregular-language

While I am studying formal languages, I see these questions.What are the answers for them?

a) The set of strings over {a, b, c} that begin with a, contain exactly two b’s, and end with cc.

b) The set of strings of even length over {a, b, c} that contain exactly one a.

c) The set of strings over {a, b} that contains an even number of substrings ba.

Best Answer

$a)$ The leading $a$ and trailing $cc$ are explicitly placed in the expression: $$a(a∪c)^∗b(a∪c)^∗b(a∪c)^∗cc$$ Any number of $a’s$ and $c’s$, represented by the expression $(a∪c)^∗$, may surround the two $b’s$.

$b)$ Let $S=\{b, c\}$. Then, in steps:

  1. The set of words of even length on the alphabet $S$ is $(SS)^∗$.
  2. The set of words of odd length on the alphabet $S$ is $(SS)^∗S$.
  3. Therefore, final regular expression is:your language is :$$(SS)^∗a(SS)^∗S∪(SS)^∗Sa(SS)^∗$$

$c)$ The set of strings over $\{a, b\}$ that contains an even number of substrings $ba$ :

$$a^*(b^+a^+b^+a)^+b^*$$

Related Question