Skip to main content
Computer Science

Return to Question

edited title
Link
Yuval Filmus
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

Irregularity of $\{0^x1^y \mid: y \nmid x\}$

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

Pumping Lemma Proof with Number Theory Irregularity of $\{0^x1^y \mid y \nmid x\}$

The language $L=\{W\in\{0,1\}^{*} | W=0^{x}1^{y}\; where \: x\geq0, y>0 \;are \;integers\; and\; y\nmid x\}$$L=\{W\in\{0,1\}^{*} \mid W=0^{x}1^{y} \text{ where } x\geq0, y>0 \text{ are integers and } y\nmid x\}$ is not regular.

How would one prove this using Pumping Lemma?

I thought about it for quite a while but couldn't quite figure it out. Lots of number theory is neccessarynecessary I'd imagine.

Pumping Lemma Proof with Number Theory

The language $L=\{W\in\{0,1\}^{*} | W=0^{x}1^{y}\; where \: x\geq0, y>0 \;are \;integers\; and\; y\nmid x\}$ is not regular.

How would one prove this using Pumping Lemma?

I thought about it for quite a while but couldn't quite figure it out. Lots of number theory is neccessary I'd imagine.

Irregularity of $\{0^x1^y \mid y \nmid x\}$

The language $L=\{W\in\{0,1\}^{*} \mid W=0^{x}1^{y} \text{ where } x\geq0, y>0 \text{ are integers and } y\nmid x\}$ is not regular.

How would one prove this using Pumping Lemma?

I thought about it for quite a while but couldn't quite figure it out. Lots of number theory is necessary I'd imagine.

added 5 characters in body
Source Link
Matt Kolson
Matt Kolson
  • 23
  • 3

The language $L=\{W\in\{0,1\}^{*} | W=0^{x}1^{y}\; where \: x\geq0, y>0 \;are \;integers\; and\; y|x\}$$L=\{W\in\{0,1\}^{*} | W=0^{x}1^{y}\; where \: x\geq0, y>0 \;are \;integers\; and\; y\nmid x\}$ is not regular.

How would one prove this using Pumping Lemma?

I thought about it for quite a while but couldn't quite figure it out. Lots of number theory is neccessary I'd imagine.

The language $L=\{W\in\{0,1\}^{*} | W=0^{x}1^{y}\; where \: x\geq0, y>0 \;are \;integers\; and\; y|x\}$ is not regular.

How would one prove this using Pumping Lemma?

I thought about it for quite a while but couldn't quite figure it out. Lots of number theory is neccessary I'd imagine.

The language $L=\{W\in\{0,1\}^{*} | W=0^{x}1^{y}\; where \: x\geq0, y>0 \;are \;integers\; and\; y\nmid x\}$ is not regular.

How would one prove this using Pumping Lemma?

I thought about it for quite a while but couldn't quite figure it out. Lots of number theory is neccessary I'd imagine.

Source Link
Matt Kolson
Matt Kolson
  • 23
  • 3