2.15.2024
Question 1: Suppose $C=\{w|w \text{ has an equal no. of 0s and 1s}\}$ is regular. Consider $s = 0^{p}1^{p}$, where $p$ is the pumping length for $C$. Suppose $s= xyz$, where $x$ is $\epsilon$. Which of the strings below would still be in $C$?
(3 points)
A. $xyz$
B. $xyyz$
C. $xyyyz$
D. all of the above
Answer
A. $xyz$Question 1: Suppose $C=\{w|w \text{ has an equal no. of 0s and 1s}\}$ is regular. Consider $s = 0^{p}1^{p}$, where $p$ is the pumping length for $C$. Suppose $s= xyz$, where $x$ is $\epsilon$. Which of the strings below would still be in $C$?
(3 points)
A. $xz$
B. $xyyz$
C. $xyyyz$
D. none of the above
Answer
D. none of the aboveQuestion 3: The minimum pumping length (mpl) for a language $A$ is the smallest integer $p$ that is a pumping length for $A$. It can be shown that the mpl is the maximum number of transitions you can take in a minimized DFA for the language without repeating a state. For the language $A$ defined by the reg. expression $01^{*}$, the mpl is $2$. What would be the mpl of the language $B$ defined by the reg. expression $0001^{*}$?
(3 points)
A. 5
B. 4
C. 3
D. 2