Regular languages question

65 Views Asked by At

Describe these languages over $\Sigma={a,b}$

  1. $\Sigma^{*}(a\cup\epsilon)b^*$
  2. $a\Sigma\Sigma^*b\Sigma\cup b\Sigma\Sigma^{*}a\Sigma$

Just making sure I understand some basic concepts... First one can be any string that is a permutation of {a,b}, second is strings of at least length 4 with at least 1 $a$ and 1 $b$ in it.

2

There are 2 best solutions below

1
On

Your first answer is correct, assuming that by "any string that is a permutation of $\{a,b\}$", you mean any string in the language $\Sigma^*$.

Your second answer isn't quite right - the given regular expression puts more constraints on where the $a$ and $b$ fall in the string.

For example, the string $abab$ is not in the language.

0
On

As Alex Kruckman noted in his answer, the language $a\Sigma\Sigma^*b\Sigma\cup b\Sigma\Sigma^*a\Sigma$ is more restrictive than you suggest. Let’s take a closer look at the first ‘piece’ of it, $a\Sigma\Sigma^*b\Sigma$. Every word in this language clearly starts with an $a$. Then $\Sigma\Sigma^*$ generates any non-empty string of $a$’s and $b$’s. Then there must be a $b$ and one more character, either an $a$ or a $b$. Think about this for a bit, and you’ll see that it matches every string of at least $4$ characters in which the first character is $a$, and the next-to-last character is $b$.

Having gone through that, we can see immediately that $b\Sigma\Sigma^*a\Sigma$ generates the strings of at least $4$ characters in which the first character is $b$, and the next-to-last character is $a$.

Thus, a word $x_1x_2\dots x_n$ belongs to this language if and only if $n\ge 4$ and either $x_1=a$ and $x_{n-1}=b$, or $x_1=b$ and $x_{n-1}=a$. We can state this more elegantly:

$\qquad\quad$A word $x_1x_2\dots x_n$ belongs to this language if and only if $n\ge 4$ and $x_1\ne x_{n-1}$.