1
$\begingroup$

Lets take the Language $$L = \{ (ab)^na^k | n \ge k \}$$

Does it dictate, that the $(ab)^n$ comes before the $a^k$ ? Or is the order irrelevant as long as it matches the $n \ge k$ criterium?

In simple terms: is the word $aaaababab \in L$ ?

And if so, does this apply for every language?

$\endgroup$
2
  • 2
    $\begingroup$ Yes, order matters. The fundamental operation is "string concatenation", for which order is important. One question: if you were happy about transposing $(ab)^n$ and $a^k$, why wouldn't you also be happy about transposing the $a$ and $b$ inside $(ab)^n$ to get a string like $aaabbabb$? $\endgroup$
    – Stef
    Feb 13 at 10:21
  • $\begingroup$ Makes sense, thank you. I've a problem trying to show that I'm able to pump up $a^k$ (pumping-lemma)... but that's one for another question. $\endgroup$
    – Robert
    Feb 13 at 10:38

1 Answer 1

1
$\begingroup$

Yes, order matters. The fundamental operation used in the definition of language $L$ is "string concatenation", for which order is important.

One question: if you were happy about transposing $(ab)^n$ and $a^k$, why wouldn't you also be happy about transposing the $a$ and $b$ inside $(ab)^n$ to get a string like $aaabbabb$?

Of course it's possible to construct languages which are stable under "anagraming", but you'll need to make that explicit in the notation, for instance:

$$L_2 = \left\{ w \in \{a,b\}^* \, \middle| \, \#_a(w) \geq \#_b(w) \right\}$$

now $L_2$ is the language of all words that contain more $a$ than $b$, regardless of order.

$\endgroup$
13
  • 1
    $\begingroup$ Thank you. This really helped me a lot! $\endgroup$
    – Robert
    Feb 13 at 11:28
  • $\begingroup$ @BaderAbuRadi I agree. But the language $L$ in the question is defined by the concatenation notation used in $(ab)^na^k$, and that is why two words $w_1$ and $w_2$ can be anagrams of eachother even though $w_1 \in L$ and $w_2 \notin L$. The language $L_2$ in my answer also consists of words which are ordered sequences of letters by definition, yet $L_2$ is agnostic of the order of letters in its words, because it doesn't use concatenation in its definition. $\endgroup$
    – Stef
    Feb 13 at 12:40
  • $\begingroup$ Words are ordered by definition, even before introducing concatenation. First we define words, then we define concatenation. $\endgroup$ Feb 13 at 12:41
  • $\begingroup$ @Stef You can look at any word as a concatenation of letters, this does not make it the reason for "order matters". Order matters because words are ordered sequences of letters. $\endgroup$ Feb 13 at 12:43
  • 1
    $\begingroup$ Your answer is fine. I just did not like the way it is written. It confuses words with concatenation of letters. At the end of the day, it does not matter as everything is consistent, but to be precise, note that $ab$ is a word and $a\cdot b$ is a concatenation of two words. Before even defining concatenation, the word $ab$ does not equal the word $ba$ as words are ordered -- that's the origin of it. Anyway, people do not make the distinction between $ab$ and $a\cdot b$, its just a side note. $\endgroup$ Feb 13 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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