Skip to main content
English; formatting; edited tags
Source Link

how can i partition Partition an infinite regular language into 2 strangedisjoint infinite regular languages?

Given any regular infinite regular language L$L$, how can iI prove that L$L$ can be partitioned into 2 strange (no intersection) regulardisjoint infinite regular languages L1,L2$L_1, L_2$? such that L1 U L2 = LThat is: $L_1 \cup L_2 = L$, $L_1 \cap L_2 = \varnothing$, and $L_1$ and $L_2$ are both both infinite and regular.

soSo far, iI thought of:

  1. using pumping lemma such that

    using the pumping lemma such that $$ \begin{gather} L_1 &= \{ xy^nz \mid \text{\(n\) is even} \} \\ L_2 &= \{ xy^mz \mid \text{\(m\) is odd} \} \\ \end{gather} $$ but couldn't prove that they are dijoint or covering $L$ completely.

  2. Using the regular language partitions $\Sigma^*$ into dijoint equivalence classes, but I haven't figured out how to determine if an equivalence class is regular or infinite.

L1 = xy^nz (n is even),
L2 = xy^mz (m is odd)
but couldn't prove that they are strange or covering L completely.

  1. using the regular language partitions \Sigma^* into strange equivalence classes but haven't figured out how to determine if an equivalence class is regular or infinite

thx

how can i partition an infinite regular language into 2 strange infinite regular languages?

Given any regular infinite language L, how can i prove that L can be partitioned into 2 strange (no intersection) regular infinite languages L1,L2? such that L1 U L2 = L

so far, i thought of

  1. using pumping lemma such that

L1 = xy^nz (n is even),
L2 = xy^mz (m is odd)
but couldn't prove that they are strange or covering L completely.

  1. using the regular language partitions \Sigma^* into strange equivalence classes but haven't figured out how to determine if an equivalence class is regular or infinite

thx

Partition an infinite regular language into 2 disjoint infinite regular languages

Given any infinite regular language $L$, how can I prove that $L$ can be partitioned into 2 disjoint infinite regular languages $L_1, L_2$? That is: $L_1 \cup L_2 = L$, $L_1 \cap L_2 = \varnothing$, and $L_1$ and $L_2$ are both both infinite and regular.

So far, I thought of:

  1. using the pumping lemma such that $$ \begin{gather} L_1 &= \{ xy^nz \mid \text{\(n\) is even} \} \\ L_2 &= \{ xy^mz \mid \text{\(m\) is odd} \} \\ \end{gather} $$ but couldn't prove that they are dijoint or covering $L$ completely.

  2. Using the regular language partitions $\Sigma^*$ into dijoint equivalence classes, but I haven't figured out how to determine if an equivalence class is regular or infinite.

Tweeted twitter.com/#!/StackCompSci/status/408275502542360577
Source Link
Tom
  • 657
  • 2
  • 8
  • 10

how can i partition an infinite regular language into 2 strange infinite regular languages?

Given any regular infinite language L, how can i prove that L can be partitioned into 2 strange (no intersection) regular infinite languages L1,L2? such that L1 U L2 = L

so far, i thought of

  1. using pumping lemma such that

L1 = xy^nz (n is even),
L2 = xy^mz (m is odd)
but couldn't prove that they are strange or covering L completely.

  1. using the regular language partitions \Sigma^* into strange equivalence classes but haven't figured out how to determine if an equivalence class is regular or infinite

thx