In Problem $14\mathrm{.}3\mathrm{.}41$ we defined the language S $=\backslash$Sigma $$a$\backslash$Sigma k of strings whose k $+1$st to last letter

exists and is a$.($Here k is an arbitrary natural.$)$ Design an NFA for this language with k $+2$

states and apply the Subset Construction to it$.$ Minimize your DFA if necessary. You now

have an example that will prove a theorem of the following form: For every n with n $>=$ n$0,$

there exists a language that has an n$-$state ordinary NFA and whose minimal DFA has f $($n$)$

states. You get to pick n$0,$ and the function f $($n$)$ should be as large as you can make it$\mathrm{.}2$

Solution:

$1$Let k be a natural, let $\backslash$Sigma $=\{$a$,$ b$\},$ and consider the regular language Sk $=\backslash$Sigma $$a$\backslash$Sigma k$,$ consisting of all those

strings whose k $+1$st to last letter exists and is an a$.$ Find the minimal DFA for each such language Sk$,$

and prove that it is minimal.

$2$Please check Piazza @$996$ for some additional notes on the problem.

$4$

P$14\mathrm{.}7\mathrm{.}5[10$ pts$]$

Here is another way to modify a $\backslash$lambda $-$NFA. For every letter move $$s$,$ x$,$ t$,$ where x is a letter in

$\backslash$Sigma $,$ add a corresponding $\backslash$lambda $-$move $$s$,\backslash$lambda $,$ t$.$ Keep the start state and final state set the same.

$($a$)$ Describe a three$-$state ordinary NFA whose language is $\{$ab$\}.$ Apply this modification

to your NFA and describe the result. What is the language of the modified $\backslash$lambda $-$NFA?

$($b$)$ If this modification is applied to a $\backslash$lambda $-$NFA with language L$,$ what is the resulting

language?

Solution:

$($a$)$ A three$-$state NFA with language $$ab$$ would have a start state q$0$ that transitions to q$1$

when given the letter $$a$$ and q$2$ from q$1$ when given the letter b$.$ q$2$ would be the final

state. Applying the modification would add lambdas for every transition. This would

allow strings to be created from empty inputs as well as the original letter inputs. The

language would still be $\{$ab$\}$

$($b$)$ If this modification is applied to a lambda NFA with language L$,$ the resulting language

would still be L$.$ Adding lambda transitions don$$t affect the strings accepted by the

system. More paths can indeed be created however the overall functionality is not

changed. In order to get from the start state to the final state, the same steps need to

be taken as in the original NFA.

$5$

P$14\mathrm{.}8\mathrm{.}9[10$ pts$]$

Formally prove the correctness of our construction for the star operator, as follows. Let N

be a $\backslash$lambda $-$NFA constructed for the regular expression $\backslash$alpha $,$ and let N $$ be the one constructed for

$\backslash$alpha $,$ with two new states and four new $\backslash$lambda $-$moves. Let L be the language of $\backslash$alpha $.$

$($a$)$ By induction on all naturals t$,$ prove that if w is any string in the language Lt$,$ then

there are w$-$paths from the start state of N $$ to both the original final state of N and

to the final state of N $.($The path to N $$s final state is a useful inductive hypothesis.$)$

$($b$)$ Prove, by induction on all paths from the start state of N $$ to either the original start

state of N $,$ the original final state of N $,$ or the final state of N $,$ that the string read

on the path is in the language L$.$

Solution:

$($a$)$ Base case: if t $=0,$ the language would just be $\{\backslash$epsi $\}.$ If t $=1,$ the regular expression

would just be $\backslash$alpha $,$ and the NFA N $$ would have N inside of it$.$ If w is a string in L$1,$

then there is a path in N from the start to the final state that has string w$.$ In N $,$

this path would also exist. A new path would also exist using a lambda move. Base

case is complete.

Assume for any t greater than or equal to $1,$ that if w is a string in Lt$,$ there exists t

paths of w from the start state in N $$ to the final state in N and the new final state.

Let w be a string in Lt$+1.$ w is made up of wa where w is in Lt and a is in L$.$ By IH

there exists a t amount of w paths in N $$

from start state to the original final state and

new final state. Since w is in Lt these paths can be made by taking a lambda move

to the new start state inside of N$.$ From start state in N$,$ there is a path that is a and

goes to the final state of N$.$ There are then t paths of wa to the original final state.

These can also be extended with a lambda move. As a result there are indeed w$-$paths

from the start state of N $$

to both the original final state of N and final state of N $$

$($b$)$ Base case: length of path is equal to $1.$ This move would be a lambda move from the

start state that would either go to the original start state, the original final state, or

the new final state N $$

$.$ This only allows lambda moves so the path would be the empty

string. The empty string is part of Lt so base case checks out.

Assume for any path t that is greater than or equal to $1,$ that the string read is in Lt

If the path is $1$ more, it can be either a symbol transition or a lambda move. If it is a

symbol transition, the first t would be checked from IH which is part of Lt$.$The final

symbol would also be in L because N is constructed from $\backslash$alpha so it would be part of the

language as well. This entire string would have to then be a part of Lt$+1$

If the path $($past the IH part$)$ ended in a lambda move, the lambda doesn$$t use a

symbol so the string would also be in Lt$+1.$ In either case the string read on the path

would be in L$$

$6$

P$14\mathrm{.}10\mathrm{.}2[10$ pts$]$

Build succ