Prove whether a language is finite or infinite.

158 Views Asked by At

Consider the language :

$L = \{w \mid w \in \{0, 1\}^∗, w \text{ has three times as many }1\text{'s as }0\text{’s}\}.$

Say whether $L$ is finite or infinite, and prove that you are correct.

I am assuming that the language described above is infinite. But, I am not sure how to set up the proof. What type of proof should I use? Contradiction, Inductive? Any help or tips appreciated.

1

There are 1 best solutions below

0
On

A subset of your language is $\{ (0 1 1 1)^n \colon n \ge 0 \}$ (each zero is followed by three ones), and that one is infinite. Thus your language is infinite.