Hints for Lab 2¶
Green¶
Question 2¶
Q2
Consider the following DFA.
Without using JFLAP, practice simulating the behaviour of this DFA using the following strings.
abba
babb
aaa
bbabba
You can use the following table to organise your work:
[...]
Produce the formal definition of the above DFA. This should consist of: the set of states \(Q\), the alphabet \(\Sigma\), the transition function \(\delta\) (in table form), the start state, and the set of accept states \(F\).
Question 3¶
Q3
Consider the following NFA:
Without using JFLAP, practice simulating the behaviour of this NFA using the following strings. (For each string, list the [sets]{.ul} of visited states, e.g. \(\{q_0\}, \{q_1,q_2\}, \{q_2,q_3\},\ldots\)).
aa
aaaa
abbaa
babb
aaaba
abbbbbbbaab
Produce the formal definition \((Q, \Sigma, \delta, q_\textbf{start}, F)\) of the above NFA.
Question 4¶
Q4
Which of the strings listed below does the following NFA accept? (Use penandpaper, not JFLAP)
10011010
01010011
00010111
0010010
There is only one accept state, and the only way to reach it is to end with 0
.
This halves the number of strings you need to try.
Question 5¶
Q5
The formal description \((Q,\Sigma,\delta,q_\text{start},F)\) of a DFA is given by
where \(\delta\) is given by the following table
Give the state diagram of this machine.
It looks like a ladder or a lift going between floors.
(u
: go up, d
: go down.)
Add the missing labels:
Question 6¶
Q6
Use JFLAP to design simple DFAs which recognize the following languages over the alphabet \(\Sigma=\{a,b\}\)
 The language of strings which begin with \(a\).
 The language of strings which end with \(b\).
 The language of strings which either begin or end with \(b\).
 The language of strings which begin with \(a\) and end with \(b\).
 The language of strings which contain the substring \(ba\).
 The language of strings with all the \(a\)'s on the left and \(b\)'s on the right
 The language strings consisting of alternating \(a\)'s and \(b\)'s.
Ensure the FA is deterministic. Check that for each state you have exactly one transition for each symbol, nothing more, nothing less.
Question 7¶
Q7
Use JFLAP to produce NFAs to recognize the following languages over \(\Sigma=\{\texttt{0},\texttt{1}\}\)
 The language of strings which begin and end with
01
.  The language of strings which do not end with
01
.  The language of strings which begin and end with different symbols.
 The language of strings of odd length.
 The language of strings which contain an even number of
0
's.  The language of binary numbers which are divisible by \(4\).
With NFAs you have freedom of using any number of transitions for each symbol, including no transitions at all.
Generally speaking, try to design a path that leads the correctly formed strings into an accept state. Then, the malformed strings get rejected because they cannot make it to the accept state.
 The language of strings which begin and end with
01
. Note that the statement also allows for the string01
to be accepted. 
The language of strings which do not end with
01
.Recall that DFAs are a special case of NFAs. For this problem, it may be easier to first create a DFA that accepts strings that end with
01
, then we flip the accepting states into nonaccepting ones, and vice versa. This will produce a DFA that accepts strings that do not end with01
, as required.\ This is a useful technique, but note that it only works for DFAs  it does not work for NFAs. 
The language of strings which begin and end with different symbols.
 The language of strings of odd length.
 The language of strings which contain an even number of
0
's. 
The language of binary numbers which are divisible by \(4\).
A number is divisible by 4 if its binary representation ends with
00
.
Question 8¶
Q8
If \(\texttt{a}\) is a symbol from an alphabet \(\Sigma\) then \(\texttt{a}^n\) denotes the string which consists of \(n\) successive copies of \(\texttt{a}\).
Similarly, if \(x\) is a string of symbols then \(x^n\) denotes the string which consists of \(n\) successive copies of \(x\). For example, \(\texttt{a}^2=\texttt{aa}\) and \((\texttt{ab})^2=\texttt{abab}\).
Let \(\Sigma=\{\texttt{0},\texttt{1}\}\). Write \(\texttt{0}^4, \texttt{1}^4, (\texttt{10})^3,\texttt{10}^3\) explicitly as strings in the usual form.
Expression  Meaning 

\(\texttt{0}^4\)  4 copies of 0 
\(\texttt{1}^4\)  4 copies of 1 
\((\texttt{10})^3\)  3 copies of 10 
\(\texttt{10}^3\)  1 followed by 3 copies of 0 
Question 9¶
Q9
If \(\Sigma\) is an alphabet then \(\Sigma^n\) denotes the set of all strings over \(\Sigma\) which have length exactly \(n\) symbols.

Let \(\Sigma=\{\texttt{a},\texttt{b},\texttt{c}\}\). Find \(\Sigma^2\).

Let \(\Sigma=\{\texttt{a},\texttt{b}\}\). Find \(\Sigma^3\).

\(\Sigma^2\): set of all strings over \(\Sigma\) which have length exactly 2 symbols.
For \(\Sigma=\{\texttt{a},\texttt{b},\texttt{c}\}\) we get:
\[\Sigma^2 = \{ \texttt{aa}, \texttt{ab}, \texttt{...}, \;\; \texttt{ba}, \texttt{...},\texttt{...}, \;\; \texttt{ca}, \texttt{...}, \texttt{...} \}\](Add the missing strings...)

\(\Sigma^3\): set of all strings over \(\Sigma\) which have length exactly 3 symbols.
For \(\Sigma=\{\texttt{a},\texttt{b}\}\) we get:
\[\Sigma^3 = \{ \texttt{aaa},\;\; \texttt{aab}, \texttt{aba}, \texttt{...}, \;\; \texttt{bba}, \texttt{...}, \texttt{...}, \;\; \texttt{bbb}\}\](Add the missing strings...)
Question 10¶
Q10
If \(\Sigma\) is an alphabet then the set of all finitelength strings over it is denoted by \(\Sigma^*\).
Let \(\Sigma_1=\{\texttt{a}\}\) and \(\Sigma_2=\{\texttt{a},\texttt{b}\}\). List the strings of length 0, 1, 2, 3, and 4 over these two alphabets. Write these in the form \(\Sigma_1^*=\{\ldots\}\) and \(\Sigma_2^*=\{\ldots\}\).
Note that
For \(\Sigma_1=\{\texttt{a}\}\):
Length  Strings 

0  \(\varepsilon\) 
1  \(\texttt{a}\) 
2  \(\texttt{aa}\) 
3  ... 
4  ... 
So,
For \(\Sigma_2=\{\texttt{a}, \texttt{b}\}\):
Length  Strings 

0  \({\varepsilon}\) 
1  a b 
2  aa ab ... ... 
3  aaa aab ... ... baa ... ... ... 
4  aaaa aaab ... ... ... ... ... abbb 
baaa baab ... ... ... ... ... bbbb 
So,
Orange¶
Question 1¶
Q1  Set of all possible languages over an alphabet
We saw in the lecture that \(\Sigma^*\) is the set of all possible strings of finite length over \(\Sigma\).
What is the set of all possible languages over \(\Sigma\)?
 \(\Sigma\) is the alphabet (finite set).
 \(\Sigma^*\) is the set of all the possible string over \(\Sigma\) (Infinite set, unless \(\Sigma=\emptyset\)).
 "A language" is a subset of \(\Sigma^*\)
 We want all the subsets of \(\Sigma^*\)
 So the answer is ...
Question 2¶
Q2  Intersection, union and difference of DFAs
Given two languages described by two DFAs, the idea is to construct a new DFA that simulates simultaneouslyrunning the given DFAs. To do this, the states of the new DFA will be pairs of states from the original DFAs.
Suppose \(\mathcal M_1=(Q_1,\Sigma,\delta_1,q_\text{start 1},F_1)\) and \(\mathcal M_2=(Q_2,\Sigma,\delta_2,q_\text{start 2},F_2)\) are DFAs recognizing \(L_1\) and \(L_2\), respectively.
Let \(\mathcal M\) be the DFA given by \((Q,\Sigma,\delta,q_0,F)\) where
and the transition function \(\delta\) is defined by
for all \((p,q)\in Q_1\times Q_2\) and \(\sigma\in\Sigma\).
Then

\(\mathcal M\) recognizes \(L_1\cap L_2\) if
\[F=\{(p,q)\mid p\in F_1 \land q\in F_2\} \quad = F_1\times F_2\] 
\(\mathcal M\) recognizes \(L_1\cup L_2\) if
\[\begin{aligned} F &= \{(p,q)\mid p\in F_1 \lor q\in F_2\} \\ &= \{(p,q)\mid p\in F_1\} \;\cup\; \{(p,q)\mid q\in F_2\} \\ &= (F_1\times Q_2) \cup (Q_1\times F_2) \end{aligned}\] 
\(\mathcal M\) recognizes \(L_1L_2\) if
\[F=\{(p,q)\mid p\in F_1 \land q\not\in F_2\} \quad= F_1\times(Q_2F_2)\]

Let the languages \(L_1\) and \(L_2\) be given by:
 \(L_1 = \{w \mid w=\texttt{a}^n \texttt{b}v \text{ where $n\geq 0$ and $v\in\Sigma^*$}\}\)
 \(L_2 = \{w \mid w=\texttt{b}^n \texttt{a}v \text{ where $n\geq 0$ and $v\in\Sigma^*$}\}\)
over \(\tt\Sigma=\{a,b\}\). Recall that \(\Sigma^*\) is the set of all strings over \(\Sigma\) of finite length.
First, design DFAs recognising \(L_1\) and \(L_2\), then use the above method to construct a DFA for
\[L_1\cap L_2=\{w\mid w \text{ has at least one $\texttt{a}$ and at least one $\texttt{b}$}\},\]then outline how it can easily be changed for \(L_1\cup L_2\) and \(L_1L_2\).

Use the same method for the language
\[\{w\mid w \text{ has an even number of $\texttt{a}$'s and each $\texttt{a}$ is followed by at least one $\texttt{b}$} \}.\]

\(L_1 = \{w \mid w=\texttt{a}^n \texttt{b}v \text{ where $n\geq 0$ and $v\in\Sigma^*$}\}\)
This means that the strings in \(L_1\) must contain at least one \(\texttt{b}\).
The \(\texttt{b}\) in \(=\texttt{a}^n \texttt{b}v\) is the first occurance, while \(v\) captures the rest of the string.

\(L_2 = \{w \mid w=\texttt{b}^n \texttt{a}v \text{ where $n\geq 0$ and $v\in\Sigma^*$}\}\)
Similarly, this means that the strings in \(L_2\) must contain at least one \(\texttt{a}\).
Note that \(n\) and \(v\) are indepent in \(L_1\) and \(L_2\), i.e. don't fall into the false assumption that they must somehow be the same. (Think of "local variables" in programming.)
Now try these concrete examples with the "theoretical construction" to demystify the notation...
Question 3¶
Q3  Complement of a language
Let us apply the results of the previous question to the special case where \(L_1=\Sigma^*\).
We get the following DFA for \(L_1\)
i.e. \(\mathcal M_1 =(Q_1,\Sigma,\delta_1,q_\text{start 1},F_1)\) where
This choice for \(\mathcal M_1\) provides us with a method to produce the complement of \(L_2\) which is defined as \(\Sigma^*L_2 = L_1L_2\). Following the result from the previous question, let
This means that the new DFA is essentially the DFA for \(L_2\) but with the accepting and nonaccepting states "flipped." (swapping roles.)
Use this observation to produce a DFA for the language
This does not always work for NFAs  give an example to show that it does not work. (Counter example)
Sketch:
First create a DFA that accepts the strings that do not satisfy the required property, then flip the accepting states into nonaccepting ones, and vice versa.
This will produce a DFA that accepts the required strings.