Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________

## Problem 1

Consider

**Example 2** from

Class 20,
which proves that the
the language

*$L_S$ = {a*^{i}:a^{j}:a^{m} ∈ {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)*.

- let
*w = a*^{|Q|}:a^{|Q|}:a^{2|Q|}
- if
*M* doesn't accept *w* then set *w' =
w*

else
- get
*x*, *y* and *z* from
P.L. v2.0
- set
*w' = xy*^{0}z

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.