Skip to main content
Computer Science

Return to Question

deleted 2 characters in body; edited title
Source Link
Yuval Filmus
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

given If $L$, a is regular language, prove thatthen $L^{|2|}=\{w_1w_2 \text{ | }\mid w_1,w_2\in L, |w_1|=|w_2|\}$ is context-free

I have found a problem about proving whether $L^{|2|}=\{w_1w_2 \text{ | } w_1,w_2\in L, |w_1|=|w_2|\}$$L^{|2|}=\{w_1w_2 \mid w_1,w_2\in L, |w_1|=|w_2|\}$ is context-free or not, knowing that $L$ is regular

So far I know that:

  • There are examples where $L$ is regular and $L^{|2|}$ is regular (for example $L=\{a,b\}$)
  • There are examples where $L$ is regular and $L^{|2|}$ is not (for example $L=\{w| w=a^N \text{ or } w= b^N\ , N\ge0\}$$L=\{w \mid w=a^N \text{ or } w= b^N\ , N\ge0\}$)

But I am not sure how to prove that it's context-free regardless of which regular language I use. I have found similar problems with the same language without imposing restrictions on which words to use, but I am not sure if those apply to this one.

given $L$, a regular language, prove that $L^{|2|}=\{w_1w_2 \text{ | } w_1,w_2\in L, |w_1|=|w_2|\}$ is context-free

I have found a problem about proving whether $L^{|2|}=\{w_1w_2 \text{ | } w_1,w_2\in L, |w_1|=|w_2|\}$ is context-free or not, knowing that $L$ is regular

So far I know that:

  • There are examples where $L$ is regular and $L^{|2|}$ is regular (for example $L=\{a,b\}$)
  • There are examples where $L$ is regular and $L^{|2|}$ is not (for example $L=\{w| w=a^N \text{ or } w= b^N\ , N\ge0\}$)

But I am not sure how to prove that it's context-free regardless of which regular language I use. I have found similar problems with the same language without imposing restrictions on which words to use, but I am not sure if those apply to this one.

If $L$ is regular then $L^{|2|}=\{w_1w_2 \mid w_1,w_2\in L, |w_1|=|w_2|\}$ is context-free

I have found a problem about proving whether $L^{|2|}=\{w_1w_2 \mid w_1,w_2\in L, |w_1|=|w_2|\}$ is context-free or not, knowing that $L$ is regular

So far I know that:

  • There are examples where $L$ is regular and $L^{|2|}$ is regular (for example $L=\{a,b\}$)
  • There are examples where $L$ is regular and $L^{|2|}$ is not (for example $L=\{w \mid w=a^N \text{ or } w= b^N\ , N\ge0\}$)

But I am not sure how to prove that it's context-free regardless of which regular language I use. I have found similar problems with the same language without imposing restrictions on which words to use, but I am not sure if those apply to this one.

Source Link
Lightsong
Lightsong
  • 239
  • 1
  • 8

given $L$, a regular language, prove that $L^{|2|}=\{w_1w_2 \text{ | } w_1,w_2\in L, |w_1|=|w_2|\}$ is context-free

I have found a problem about proving whether $L^{|2|}=\{w_1w_2 \text{ | } w_1,w_2\in L, |w_1|=|w_2|\}$ is context-free or not, knowing that $L$ is regular

So far I know that:

  • There are examples where $L$ is regular and $L^{|2|}$ is regular (for example $L=\{a,b\}$)
  • There are examples where $L$ is regular and $L^{|2|}$ is not (for example $L=\{w| w=a^N \text{ or } w= b^N\ , N\ge0\}$)

But I am not sure how to prove that it's context-free regardless of which regular language I use. I have found similar problems with the same language without imposing restrictions on which words to use, but I am not sure if those apply to this one.