1. Problem 6: For each language over alphabet $\Sigma=\{a,b\}$, provide two strings that are members and two strings that are not members. 2. a) Language $a^*b^*$: strings with zero or more $a$s followed by zero or more $b$s. - Members: $\varepsilon$ (empty string), $aaabbb$ - Non-members: $aba$, $bab$ 3. b) Language $a(ba)^*b$: strings starting with $a$, followed by zero or more repetitions of $ba$, ending with $b$. - Members: $ab$, $ababb$ - Non-members: $aab$, $baba$ 4. c) Language $a^* \cup b^*$: strings of all $a$s or all $b$s (including empty string). - Members: $aaa$, $bbb$ - Non-members: $aba$, $bab$ 5. d) Language $(aaa)^*$: strings consisting of zero or more repetitions of $aaa$. - Members: $\varepsilon$, $aaaaaa$ - Non-members: $aa$, $aaaa$ 6. e) Language $\Sigma^* a \Sigma^* b \Sigma^* a \Sigma^*$: strings containing $a$, then $b$, then $a$ in order anywhere. - Members: $aba$, $baaba$ - Non-members: $aab$, $bba$ 7. f) Language $(a \cup ba \cup bb) \Sigma^*$: strings starting with $a$, $ba$, or $bb$. - Members: $aab$, $bab$ - Non-members: $b$, $ab$ 8. Problem 7: Convert regular expressions to nondeterministic finite automata (NFA). 9. a) Regular expression $(0 \cup 1)^* 000 (0 \cup 1)^*$: strings over $\{0,1\}$ containing substring $000$. - The NFA has states tracking the progress of matching $000$ with transitions on $0$ and $1$ accordingly. 10. b) Regular expression $(((00)^* (11)) \cup 01)^*$: strings formed by zero or more repetitions of either $00$ repeated any number of times followed by $11$, or $01$. - The NFA combines NFAs for $(00)^* (11)$ and $01$ with a star operation. Slug: "language membership" Subject: "theory of computation" Desmos: {"latex":"","features":{"intercepts":false,"extrema":false}} q_count: 2