\documentclass[10pt]{article}

\usepackage{hevea,xspace}

\oddsidemargin 0cm
\textwidth 17cm

\newcommand{\ignore}[1]{}
\newcommand{\ie}{{\em i.e.},\xspace}
\begin{document}

\thispagestyle{empty}

\begin{center}
{\bf CS 3100 -- Models of Computation -- Fall 2010}\\
{\bf Notes 8, Posted online: September 16, 2010 }
\end{center}

These problems will be helpful for Midterm-1.
%
More solutions will be worked out.
%
The midterm exam itself won't be this long!
%
Many of the actual questions will be a subset of these questions 
with small variations. 

Midterm-1 will be open book and notes. 
However, please do not depend on
this material (except for quick reassuring peeks). It will not help
shuffle through books/notes during the midterm.

\subsubsection*{Short Questions}


\paragraph{Please say true or false, giving reasons in at least two good sentences}

\begin{enumerate}
\item Alphabets can contain $\varepsilon$.

{\sf
False; alphabets never include $\varepsilon$.
}

\ignore{
$\bullet$
True or False, stating reasons: 
Alphabets of ordinary NFAs and DFAs can contain $\emptyset$

$\diamond$
Alphabets of ordinary NFAs and DFAs
are not sets.
 They are uninterpreted units of information
 that are processed by DFAs.
Now we can define generalized NFA/DFA that have
 alphabets that are sets.
}

\item All alphabets are non-empty.

{\sf
True. Alphabets must be non-empty.
}

\item The alphabet of a DFA can be infinite.

{\sf
False. DFAs by definition have a finite alphabet.
}

\ignore {
$\bullet$
Someone claims that they have drawn a DFA transition table
for a DFA over the alphabet
\\ $\{x\;\mid\; x\; is\; an\; even\; number\}$.
How would you respond to this claim?

$\diamond$ This claim is false because such a DFA will have
to have an infinite number of transitions from each state.
This is not allowed.
}

\item The alphabet of an NFA can contain $\varepsilon$.

{\sf
False. The alphabet of an
 NFA cannot contain $\varepsilon$ (same for a DFA).
}

\ignore{
$\bullet$
Draw a DFA whose language contains $\varepsilon$ and
nothing else.

$\diamond$ An NFA with a start state that is also final,
with no transitions would do.
}

\item There are only a finite number of languages over a given
  alphabet.

{\sf
False. One can have infinitely many languages over any alphabet.
}

\ignore {
$\bullet$
Show that there are infinitely many singleton languages (languages
containing exactly one string) over a singleton alphabet (alphabet
containing exactly one symbol).

$\diamond$
One can have different
languages, each containing single strings $a$, $aa$, $aaa$,
etc.
}

\item $\{\}^*$ and $\{\varepsilon\}^*$ are different languages.

{\sf
False. They are the same language.
}

\item $\{\}^*$ and $\{\varepsilon\}$ are different languages.

{\sf
False. They are the same language.
}

\ignore {
$\bullet$
List all strings in the language

$\{a, aba\} \; \{\varepsilon, ba\}$

Here juxtaposition of two languages denotes conjunction.

$\diamond$
The strings are $a$, $aba$, and $ababa$.
}

\item NFAs can always be complemented by
  exchanging final (accepting) and non-final (rejecting) states.

{\sf
False. Consider an NFA $N$ over alphabet
$\{a\}$ with one initial state I going to two different 
states A (accepting) and B (rejecting), with both transitions 
labeled by $a$. A and B have no outgoing transitions.
This NFA accepts $a$, but the erroneous complementation
procedure gives an NFA with $a$ in its language as well.
}



\item All DFAs can be redrawn to have exactly one final state,
  resulting in a language-equivalent DFA.

{\sf
This is false. Consider the minimal DFA for the language
$\{a,aa\}$
over $\{a\}^*$.
Such a DFA must have two distinct final states.
}

\ignore{
$\bullet$
 All NFAs can be redrawn to have exactly one final state,
  resulting in a language-equivalent NFA.

$\diamond$
True. Use $\varepsilon$ jumps to a new final state from the previous
final states, after making the previous final states non-final.

}

\item NFA intersection can be performed using the same algorithm
  as used for DFA intersection (marching the machines together,
  labeling a next state as accepting if both next states are
  accepting), and the result will be a single NFA for the intersection
  of the languages.

{\sf
For NFAs without $\varepsilon$ jumps, this works. 
We must adapt this algorithm for NFAs with $\varepsilon$ jumps.
The question is how to treat $\varepsilon$ jumps in one NFA versus
 non-$\varepsilon$ jumps in another. If we can do the 
$\varepsilon$-closure after every jump and pull in those states also, 
then it can be made to work.
So the answer is ``no, not without doing extra work concerning
$\varepsilon$.''
}

\ignore{

$\bullet$
Given a regular language $L$, define its reversal closure to
be a new language $L^{'}$ that contains all the strings in
$L$ and their reverses. Show that reversal closure 
preserves regularity.
%
Hint: think of how you will build up $L^{'}$ given $L$.

$\diamond$
Reversal closure of $L$ is obtainable by taking the reverse
of $L$ and performing a set union. Both these operations
preserve regularity.

}


\item Every DFA is also an NFA in every respect (including
  how their next-state functions are defined).

{\sf 
False. The next-state function of an NFA specifies sets of
states as the target of every jump.
}

\item Given a DFA of $M$ states and another of $N$ states,
  there is a straightforward algorithm to obtain a DFA
  of no more than $M\times N$ states that represents the union
  of these two DFAs.

{\sf
True. The standard algorithm.
}

\end{enumerate}

\paragraph{Please give short answers in one to two (sometimes three) sentences}

\begin{enumerate}


\item Please give an example of an NFA $N$ such that it cannot
  be starred without adding an extra initial state.
  I am referring to the standard NFA starring procedure here.

{\sf
Consider an NFA 
\begin{verbatim}
Initial state = I
Final state = F
Transitions:

I -a-> F
I -b-> I

\end{verbatim}
This NFA accepts strings ending in {\tt a} with any number of {\tt b}s before it.
However a string of just {\tt b}s is not accepted. 
%
If we star this NFA by turning the state I into a final state and putting an
$\varepsilon$ jump from F to I, we will accept strings of just {\tt b}s, which
cannot be in the star of the language of this NFA.
}

\item The reverse of a language is defined to be a set containing
  all the original strings, except each string appears reversed.
  What is in the reverse of $S=\{\varepsilon, a, aa, aaa, aab, aba\}$ that
  is not in $S$?

{\sf
$baa$ is not present in the reverse of $S$.
}

\item There are languages $L$ such that they are identical
  to their reverse. What are these languages called?

{\sf
Palindromic languages.
}

\item What is the alphabet of a GNFA (generalized NFA) that you
  obtain during DFA to RE conversion?

{\sf
Regular expressions.
}


\item Describe a way to obtain an NFA $n_2$ from a given
  NFA $n_1$ such that the language of $n_2$ is the
  reverse of the language of $n_1$.
  Hint: you can retain all the states of $n_1$ and
  do something simple with the edges, and also add one extra state.

{\sf
(i)~Introduce a new initial state. 
(ii)~Turn all final states into non-final states, introducing a jump from this initial state
to the former final states through $\varepsilon$.
(iii)~Turn the initial state into a final state (it may have temporarily become non-final
in step (ii).
(iv)~Reverse all transitions.
This construction yields the reverse of a language because any string from the initial
state to a final state can now be traced backwards from the new initial state to the original
initial state.
}

\item Does this NFA reversal algorithm work for DFAs too (in the sense of yielding a DFA which represents
the reverse of the language of the original DFA)? Why or why not?

{\sf
Consider two transitions in this DFA that are labeled by $a\in\Sigma$ entering one state $s$.
After the steps described above, we will have $s$ exiting through $a$ to two possibly different
states---\ie, we end up introducing non-determinism.
So we may not obtain a DFA as a result; but we can obtain an NFA
 that describes the reverse of the language of the original DFA. 
}

\item Are regular languages closed under reversal? Explain of course,
  relating to questions you have already answered.

{\sf
Yes, they are, because we can reverse NFAs, obtaining NFAs that represent the reversed language.
}

\item Is the language of palindromes over a singleton
  alphabet (alphabet with exactly one symbol) regular?

{\sf
Yes because any language that includes {\em all} palindromes over a singleton alphabet $\Sigma=\{a\}$
is nothing but $a^*$.
}


\end{enumerate}

\subsubsection*{Long Answer Questions}

\begin{enumerate}

\ignore{

\item

$\bullet$
Draw a DFA $D_1$ for the language $L_{odd}$ over $\{0,1\}^*$  containing all (and only) the 
even length strings over this alphabet.
%
Now draw a DFA $D_2$ for the language $L_{no101}$ over $\{0,1\}^*$ 
containing all and only those strings without a $10$ in them.
%
Obtain the intersection of these languages.
%
Briefly argue the correctness of the resulting DFA.
}


\ignore{

\item 

$\bullet$
Draw an NFA $N$ for the language over $\{0,1\}$ that contains
an odd number of $1$s OR an even number of $0$s.

Obtain  a DFA equivalent to $N$. Minimize this DFA through the
DFA minimization algorithm.
}


\item Draw a DFA for the set of binary
  strings that are fed MSB-first
  and are evenly divisible by seven.
  Show the transitions out of states 3 and 4 fully.
  There is no need to show the remaining transitions.

{\sf
The state transition equations are as follows.

$N\%7 \shortstack{0 \\ $\longrightarrow$} (2.(N\%7))\%7 $

$N\%7 \shortstack{1 \\ $\longrightarrow$} ((2.(N\%7))\%7 + 1)\%7 $

Thus, out of state $3$, we will have

$3 \shortstack{0 \\ $\longrightarrow$} 6 $

$3 \shortstack{1 \\ $\longrightarrow$} 0 $

Work out the moves out of $4$ similarly.

}

\ignore{
$\bullet$
Draw a DFA for the set of binary
  strings that are fed MSB-first
  that are evenly divisible by five.
  Show the transitions out of states 3 and 4 fully.
  There is no need to show the remaining transitions.

$\diamond$
The state transition equations are as follows.

$N\%5 \shortstack{0 \\ $\longrightarrow$} (2.(N\%5))\%5 $

$N\%5 \shortstack{1 \\ $\longrightarrow$} ((2.(N\%5))\%5 + 1)\%5 $

Thus, out of state $3$, we will have

$3 \shortstack{0 \\ $\longrightarrow$} 1 $

$3 \shortstack{1 \\ $\longrightarrow$} 2 $

}

\item Show using the Pumping lemma that 
  the language of Palindromes $L_{pal}$
  over the alphabet $\{0,1\}$
  is not regular.

{\sf

Consider a DFA of $k$ states being able to recognize
this language.
Consider the string $0^k 1 0^k$ which is a palindrome.
By ``pumping up'' within the first $0^k$ strings, we can obtain
a string that is not in $L_{pal}$.
(By pumping up, we are introducing extra $0$s before the $1$.)

}

\item Write down a regular expression for the
  language $L_{epis1}$---namely
  all strings over $\{0,1\}$ such that every even position is a $1$.

{\sf

$   ((0+1)1)^* (0+1+\varepsilon) $

}


\item How would you change this
  for
  all strings over $\{0,1\}$ such that every even position is a $1$
  for all strings that begin with a $1$, and for strings that
  begin with a $0$, there are no constraints? Argue why
your answer is correct.

{\sf

$  1 (1 (0+1) )^* (1 + \varepsilon)  \;\; + \;\; 0 (0+1)^* $

We provided for the constraints in the first part of the RE
by insisting on there being a $1$ in the right place for
 all strings---of odd or even lengths.
The ``start with $0$'' was handled simply.

}



\ignore{
$\bullet$ 
Write down a regular expression for the 
 language $L_{episNot1}$---namely
 all strings over  $\{0,1,2\}$ such that every even position is 
 something other than a $1$.

$\diamond$
The solution is similar to the ``every even position is a $1$
except we have to insist on seeing $(0+2)$.

}


\item Describe the complement of $L_{allEpsAre1s}$ in English.
  Write down four of the shortest strings in this language
  (in case of a tie for lengths, choose any string of the same
  length group). Call this language $L_{oneEpIs0}$.

{\sf

The complement will have one even position that is a $0$.
As discussed in class, it consists of strings like

$00$, $10$, $000$, and $100$.


}
  
\item Write down a regular expression for $L_{oneEpIs0}$.

{\sf

The first ``broken'' even position is after a few good
even positions, if any.

This is what the following RE says.

Once broken, we don't care what happens:

$( (0+1) 1 )^* \; ( (0+1) 0 ) \; (0+1)^* $

}

\item Obtain a DFA $D_{allEpsAre1s}$ 
  for $L_{allEpsAre1s}$. Use any method
  (short-cuts are OK so long as you are sure about your work).

%{\sf 
%ANSWER.
%
%}

{\sf 
ANSWER.

This will be a simple DFA. 

Let us denote initial states  by Ixx (xx means anything; e.g. I23 etc)

Initial and final states by IFxx

Final states by Fxx

Non-final states by any other name.

Then we have the following DFA:

\begin{verbatim}
IF --0,1--> F0

F0 --1--> IF

F0 --0--> A

A  --0,1--> A
\end{verbatim}

}


\item Obtain a DFA $D_{oneEpIs0}$ 
  for $L_{oneEpIs0}$. Use any method
  (short-cuts are OK so long as you are sure about your work).

{\sf
ANSWER.

\begin{verbatim}
I --0,1--> B

B --1--> I

B --0--> F1

F1  --0,1--> F1
\end{verbatim}
}


\item Show how to systematically arrive at 
  $D_{allEpsAre1s}\;\cap\; \overline{D_{oneEpIs0}}$. 
  Here, the ``overline'' means {\em complement}.
  {\em Before you begin your work,} what answer do you expect
    to obtain?
  Now finish your work and please explain whether you obtained
  the expected answer?

{\sf
We do the product construction, obtaining  back

  $D_{allEpsAre1s}$

}

\item Show how to systematically arrive at 
  $D_{oneEpIs0}\;\cap\; \overline{D_{allEpsAre1s}}$. 
  Here, the ``overline'' means {\em complement}.
  {\em Before you begin your work,} what answer do you expect
    to obtain?
  Now finish your work and please explain whether you obtained
  the expected answer?

{\sf
We do the product construction, obtaining  back

  $D_{oneEpIs0}$

}

\item Obtain an NFA $N_{errc}$ that corrects all one-bit errors
  with respect to the language $(0+1)^* 0101 (0+1)^*$.
  Directly draw this NFA without any intermediate steps.
  This NFA is not the NFA for $RE_{orig} = (0+1)^* 0101 (0+1)^*$, but
  all strings that are different in {\em up to one position}
  with respect to $R_{orig}$. That is, error-free strings plus
  strings corresponding to one-bit errors are both included.

{\sf

We discussed this in class.

}

\item Obtain a regular expression $RE_{errc}$ that captures
  the correction of all one-bit errors
  with respect to $RE_{orig}$.
  That is, this is an RE for 
  all strings that are different in {\em up to one position}
  with respect to $R_{orig}$. 
  Directly write this RE.

\item Show that $N_{errc}$ and $RE_{errc}$ have the same minimal DFA.

\item Review RE to NFA, NFA to DFA, and DFA to RE algorithms. Know
  how to apply them for simple problems.

\item Review the DFA minimization procedure. Know how to apply
  it for simple problems.

{\sf

Start with all final states in one equivalence class and
non-final ones in another equivalence class.
%
These are already distinguished states.
%
Move the equivalence classes through each symbol.
%
If the target states under the same symbol are distinguished,
split the equivalence classes.

We will work out a simple problem. 

%Consider the DFA
%
%\begin{verbatim}
%I -0-> A
%A -1-> FB
%FB -0-> C
%C  -1-> FD
%FD -0-> C
%\end{verbatim}
%
%Here FB and FD are final states. All other transitions not shown
%go to the trap state.
%
%We can create an equivalence class $\{I,A,C\}$ and $\{FB,FD\}$.
%Now, 

}

\item Is the language 
\[ L_{sqr} = \{ a^{n^2} \;\mid\; n\ge 0\} \]
regular?
This language has strings of $a$s of lengths that are perfect squares.

{\sf
No. 
There are two ways to prove it.

\begin{enumerate}
\item {\sl Using the Pumping Lemma:}
  If we assume that there is a $k$-state DFA for $L_{sqr}$, pick any string 
  $z$ in $L_{sqr}$ of length greater than $k$.
  This means that we should be able to split $y$ into $uvw$ with $\mid uv\mid \leq k$
  (length of $uv$ is $\leq k$) and $\mid v\mid > 0$.
  Furthermore, we should be able to generate strings in $L_{sqr}$ 
  by iterating $v$.
  That is, for all $i\ge 0$, $uv^iw \in L_{sqr}$. 
  This is impossible for a language that only has perfect squares as the lengths of its 
  strings.
  Perfect squares cannot be generated by adding successive $\mid v\mid$ lengths.
  In other words, $uv^iw$ describe a family of lengths that lie on a straight-line slope
  which cannot be on a square curve.

\item {\sl Distinguishable Pairs of Strings Approach:}
  The creative part is to find sets of pairs of distinguishable strings.
  Let $L_{sqr}$ itself be the set. 
  Again, knowing how squares are, we can assert this:
  Suppose we take two successive strings $s_1$ and $s_2$ of lengths $m$ and $n$ in $L_{sqr}$ (that is,
  $m=p^2$ and $n=(p+1)^2$ for some natural number $p$).
  Now consider a string $z$ of length $(n-m)$.
  We know that $a^{m+z}\in L_{sqr}$.
  We can prove that $a^(r+z)$ is not in $L_{sqr}$ for all $r$.
  %
  That is, if we have a set of perfect squares, and if we take the difference between
  two adjacent perfect squares $m$ and $n$, we cannot generate 
  any perfect square by adding this difference to $m$.
  %
  For example, in the set
  $\{1,4,9,16,25,36,49,64,\ldots\}$, $36-25=11$, but adding $11$ to any of the numbers except to 
  $25$ cannot
  yield anything in this set.

\end{enumerate}
}

\item Suppose language $A$ is unknown to be regular or not.
  Suppose  $B$ is known  regular. Suppose we obtain
  $AandB = A\cap B$ and
  find  $AandB$ to be non-regular. Now what can we say about $A$ (regular
  or not)? (Hint: Consider $A$ to be
  the set of strings over $\{0,1\}$ with an equal
  number of $0$s and $1$s, and 
  let $B$ be $0^* 1^*$.)

{\sf
We can say that $A$ is non-regular. If it were regular, then $AandB$ must
be regular. It is not. For the given examples,
$AandB$ is $\{0^n 1^n \;\mid\; n\ge 0\}$.
}

\item Suppose language $A$ is unknown to be regular or not.
  Suppose  $B$ is known  regular. Suppose we obtain
  $AandB = A\cap B$ and
  find  $AandB$ to be regular. Now what can we say about $A$ (regular
  or not)? (Hint: Consider $A$ to be $L{0^n1^n}$ and $B$ be $\emptyset$.)

{\sf
We cannot say anything about $A$.
Whether it is regular or not, the intersection of $A$ yields the empty
set (empty language).
%
Empty languages are regular because they can be accepted by an NFA
with a single start state with no transitions, and with no final state.
}

\item Show using the Pumping Lemma  that
  \[ L_{a^mb^n} = \{ a^m\; b^n \;\mid\; m > n \} \]
  is non-regular. You are required to use these facts/methods:
  \begin{enumerate}
  \item That   \( L_{a^mb^n} = \{ a^m\; b^n \;\mid\; m < n \} \) is non-regular.
  \item Regular languages are closed under reversal.
  \end{enumerate}

{\sf
If $L_{a^mb^n}$ is regular, so is its reverse.
Take the reverse of $L_{a^mb^n}$. 
It is a similar language except $m<n$.
Let it be regular with a $k$-state DFA.
Now consider a string $a^k b^r$ for $r>k$ in the reversed language.
We can pump the $a^k$ portion to come outside of this language.
Hence the reversed language, and hence $L_{a^mb^n}$ itself are non-regular.
}

\end{enumerate}


%  [ exam a^m b^n :  n < m pumping proof . use reverse and closure.. ]

%  [ exam  a^m b^n : m < n - pumping proof ]


\end{document}
%--end
