Given are 2 different languages and I'd like to know if I understand them correctly.

L ⊆ ∑* is a regular language.

  1. cycle(L) = {vu ∈ ∑* | uv ∈ L}

  2. L/2 = {x ∈ ∑* | ∃y ∈ ∑* : xy ∈ L, |x| = |y|}

I need to know that because the actual task is to show that these languages are regular by either describing how you build a DFA or NFA for them.

But I just like to know if I understood them correctly.

So 1. means that every word has an existing reverse.

As example we have word aaa and bab, if we concatenate them, we have aaabab. Now the language says that there is also a word babaaa

  1. Means that we have two words of same length and we concatenate them?

For 1. it is not quite the reverse; it happened to be a reverse in your example. So if $u = aab$ and $v = abb$ and $uv \in L$, then you know $vu = abbaab \in \text{cycle}(L)$, but you wouldn't be able to say that $bbabaa = v^Ru^R \in \text{cycle}(L)$.

For 2. it is not that you want the concatenation of two strings of equal length, but rather you only want the first half of even-length strings in $L$. That is, if, say, $aabbabbabb \in L$, then $aabba \in L/2$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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