---
# System prepended metadata

title: 'Lab 1 (Jax Seiler, Ally Rogers, Kevin Wang)'

---

# Lab 1 (Jax Seiler, Ally Rogers, Kevin Wang)

Problem 1  

1. 0, 1, 10  
2. Yes, if $k = 0$  
3. Countably infinite - there is no upper limit on the length of strings generated, so there are infinitly many strings possible.  
4. If $\Sigma$ = $\emptyset$, there is only one possible string, the empty string.  
5. Yes - see above.  

Problem 2  

1. $ab$ and $aa$ are distinguishible. For example, if $z = ba$, then $xz = abba \in L_1$ and $yz = aaba \notin L_1$. $aaaa$ and $aaab$ are indistinguishible, because no $z$ exists such that $xz \in L_1$ or $yz \in L_1$.  
2. Assume we are still using $\Sigma = \{a, b\}$. $a$ and $b$ are distinguishable with $z = a$; $xz = aa \notin L_2$ and $yz = ba \in L_2$. $aa$ and $bb$ are distinguishible with the same $z$. $a$ and $aa$ are indistinguishable; any $z$ ending with $a$ gives $xz = a...a \notin L_2$ and $yz = aa...a \notin L_2$. Similarly, any $z$ ending with $b$ gives $xz = a...b \in L_2$ and $yz = aa...b \in L_2$. The same logic applies for $b$ and $bb$, as well as $ab$ and $aa$.  
3. Two strings are indistinguishable when the machine will yield the same acceptance state for both strings. Additionally, if any string is appended to each, this property remains.  