Name: ____________________________________________________ Alpha: _____________________

## Problem 1

Consider Example 2 from Class 20, which proves that the the language $L_S$ = {ai:aj:am ∈ {a,:}*| m = i + j} is not accepted by any DFA. The proof is an algorithm that takes a machine M and returns a string w' that the machine miscategorizes with respect to $L_S$. Given the machine:
Algorithm from Class 20, Example 2
Input: machine M = (Q,Σ,δ,s,W)
Output: string w' such that either w' ∈ $L_S$ but w' ∉ L(M), or w' ∉ $L_S$ but w' ∈ L(M).
1. let w = a|Q|:a|Q|:a2|Q|
2. if M doesn't accept w then set w' = w
else
• get x, y and z from P.L. v2.0
• set w' = xy0z

What string does this algorithm produce? [ Note: there are several possible right answers depending which exact x,y,z you assume the Pumping Lemma Version 2.0 returns. Just be sure you choose an x,y,z for which y really corresponds to a loop in the computation. ] Tell me clearly what w is in step 1, what w' is and, if the "else" is executed, what x, y and z are.

## Problem 2

Prove that the language $L_\text{pars}$ of properly parenthesized lists of a's is not accepted by any DFA. Note: ((a,a),((a)),a) is properly parenthesized, while )a,(a) is not, nor is (a),((a)),a))). So more paren's than needed are fine, they just have to all match up properly.