0
$\begingroup$

I need help understanding the language L above.

These are my understanding:
- w = uu is a concatenation of u
- La(1*01*) can be expressed in regular language i.e. r1 = 1*01* so La(r1)
- also we have regular expression property of concatenation: L(r1r2) = L(r1)L(r2)

So base on my understanding the language L can be simplified to

I'm not quite sure about this.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

No, your simplification is wrong.

Consider, as a simpler case, $A=\{a,b\}$ and $L'=\{ w \mid w=uu , u\in A\}$. Then, $L'=\{aa,bb\}$.

Instead, if we apply your simplification and write $L''=AA$ then we have $L''=\{aa,ab,ba,bb\}$ which is a larger language, since we forgot that both $u$'s in $w=uu$ must be the same word.

Keeping that into account, your original language $L$ seems to be $\{1^n01^m1^n01^m \mid n,m\geq 0 \}$

Improve this answer
$\endgroup$
2
  • $\begingroup$ So we ignored ab and ba in the set because uu is an element of A and must be the same character. $\endgroup$
    – tramyardg
    Commented Dec 1, 2018 at 21:39
  • $\begingroup$ @tramyardg It must be the same word, repeated. In this case $A$ only contains single-letter words, but in general it can contain longer words, as in your example. $\endgroup$
    – chi
    Commented Dec 1, 2018 at 22:08

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.