Language made by a regular expression

41 Views Asked by At

I created a language from this regular expression but I'm not sure about it, especially where I wanted to use the $w$ to express a sequence of terminals.

The expression:

$r = a a ^{*} (b + bb + bbb) (a + b) (a + b) ^ {*}$

The alphabet:

$\Sigma = \{a,b\}$

The language:

$L = \{ a a ^{n} b b^{m} w^{p} : n \geq 0, m \leq 2, p \geq 1, $w is any sequence of a's and b's including $\lambda$ $ \}$

1

There are 1 best solutions below

0
On BEST ANSWER

Your description of $L$ is not wrong, but it’s a bit clumsy. For instance, instead of writing $aa^n$ and requiring $n\ge 0$, you can write just $a^n$ with the requirement $n\ge 1$. You can also combine $bb^m$ into $b^m$ by changing the requirement on $m$. More important, there’s no need for an exponent on $w$, since $w$ is already an arbitrary string of $a$’s and $b$’s. If you make these changes, you get

$$L=\left\{a^nb^mw\in\{a,b\}^*:n\ge 1,1\le m\le 3,\text{ and }|w|\ge 1\right\}\;.$$

In other words, the language consists of those words that start with a string of one or more $a$’s, followed by one to three $b$’s, followed by any non-empty string of $a$’s and $b$’s.