Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

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.

share|improve this answer
    
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. –  Tara B Feb 26 '13 at 17:27
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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