Q$7$ True$/$ False

$3$ Points

True$/$ False: Every proper subset of a regular set is regular.

True

False

True$/$ False: Every proper subset of a nonregular set is nonregular.

True

False

True$/$ False: The complement of a regular set is regular.

True

False

True$/$False: The complement of a nonregular set is nonregular

True

False

True$/$ False: The union of any two regular sets is regular.

True

False

True$/$ False: The union of two nonregular sets is nonregular.

True

$()$ False

Q$8$ Pumping Lemma

$2$ Points

Select all and only true statements.

All regular languages have pumping lengths.

To prove that a language is regular, it's enough to show that it has a pumping length.

To prove that a language is nonregular, it's enough to show that it does not have any

pumping lengths.

To prove that a specific positive integer is not a pumping length for a given language, we

need to show that all strings are not "pumpable" relative to that length.

To prove that a specific positive integer is not a pumping length for a given language, we

need to show that there is a string in that language that is longer than that number and

that is not "pumpable" relative to that length in that language.

Q$9$ Pumping length

$3$ Points

Definition A positive integer $p$ is a pumping length of a language $L$ over $$ means that, for each

string $sin{}^{**},$ if $|s|p$ and $sinL,$ then there are strings $x,y,z$ such that $s=xyz$ and $|y|>0,$

for each $i0,x{y}^i$zinL, and $|xy|p.$

In particular, this means that a positive integer $p$ is not a pumping length of a language $L$ over

$$ iff

EEs$(|s|p^{{?}^{?}}sin{L}^{{?}^{?}}$AAxAAyAAz$((s=xy{z}^{{?}^{?}}|y|>0^{{?}^{?}}|xy|p)$EEi$(i{0}^{{?}^{?}}x{y}^{i}z!$inL$)))$

True$/$ False: A pumping length for $A_1=\{1,01,001,0001,00001\}$ is $p=4$

True

False

True$/$ False: A pumping length for $A_2=\{0^{j}1|j0\}$ is $p=3$

True

False

True$/$ False: For any language $A,$ if $p$ is a pumping length for A and $p^{\text{'}}>p,$ then $p^{\text{'}}$ is also a

pumping length for $A.$

True

False