1
$\begingroup$

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.

$\endgroup$

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ But note that 'any string that is a permutation of $\{a,b\}$' is not a usual way of saying 'any string in the language $\Sigma^*$. A permutation is not a string. $\endgroup$ Commented Feb 26, 2013 at 17:27
1
$\begingroup$

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}$.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.