Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________

Problem 1

Consider Example 2 from class, which proves that the the language $L_S = \{a^i:a^j:a^m \in \{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, 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|}:a^{2|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' = xy^0z$

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

Let $L_\text{pars}$ be the language of properly parenthesized lists whose elements are either a's or are themselves lists. For example: ((a,a),((a)),a) and (a,(a,(a)),(a),((a))) are properly parenthesized, and thus in $L_\text{pars}$, 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. Prove that the language $L_\text{pars}$ is not regular, i.e. cannot be defined by a finite automaton or regular expression.