TC

Quiz 1

Which of the following sentences is false?

1. (a + b)^∗a^∗ and ((a + b)a)^∗ generate the same language
2. ((a + b)a)^∗ and (aa + ba)^∗ generate the same language
3. ((a + b)a)^∗ generates the language reverse of the one generated by (a(a + b))^*
4. (a + b)^∗a^∗ and (a^∗b)^∗a^∗ generate the same language

Quiz 2

Given the following equation between languages X = (a + \lambda)X + b\ , which of the following sentences is false?

1. X=a^*b is a solution
2. X=a^*b^* is a solution
3. X=a^*b^+ is a solution
4. X=a^+b^+ is a solution

Quiz 3

Given L=\{w\in \{0,1\}^* \mid \mathrm{value}_2(w)\in 3\mathbb N\}. Consider the sets

\{0,1\}\qquad \{0,1,10\}\qquad\{0,1,10,11\}

How many of them are L-distinguishible?

1. 0
2. 1
3. 2
4. 3

Quiz 4

You want to show that L=\{a^nb^m \mid n\neq m\} is not a regular language applying the pumping lemma directly to L.

Given the pumping length p, you choose a word w as in the argument to apply the pumping lemma. Which of the following possibilities has a chance to make the rest of the argument correct?

1. w=a^{p!}b^{p+p!}
2. w=a^{p+1}b^{p}
3. w=a^pb^{p+p!}
4. w=a^{p}b^{p+1}