Hints for Lab 2¶

Green¶

Question 2¶

Q2

QuestionSimulationFormal specification

Consider the following DFA.

DFA diagram

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$.

\[\begin{array}{rcl} Q &=& \{\text{A},...,...,...\}\\ \\ \Sigma &=& \{...,...\}\\ \delta &:& \begin{array}{|r||c|c|} \hline & \texttt{a} & \texttt{b} \\ \hline\hline \text{A} & ... & ...\\ \text{B} & ... & ... \\ \text{C} & ... & ... \\ \text{D} & ... & ... \\ \hline \end{array}\\ \\ q_\text{start} &=& ...\\ F &=& \{ ...\}\\ \end{array}\]

Question 3¶

Q3

QuestionSimulationFormal specification

Consider the following NFA:

DFA diagram

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.

\[\begin{aligned} Q &= \{q_0,...,...,...,...,...\}\\ \Sigma &= \{...,...\}\\ \\ \delta &: \begin{array}{|r||c|c|} \hline & \texttt{a} & \texttt{b} \\ \hline\hline \to* q_0 & \{...,...\} & \emptyset \\ q_1 & \{...,...\} & \emptyset \\ q_2 & \{...\} & ... \\ q_3 & ... & \{...,...\} \\ q_4 & ... & \{...\} \\ * q_5 & ... & ... \\ \hline \end{array}\\ \\ q_\text{start} &= \ ... \\ F &= \{..., ...\}\\ \end{aligned}\]

Question 4¶

Q4

QuestionHint

Which of the strings listed below does the following NFA accept? (Use pen-and-paper, 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

QuestionHint

The formal description $(Q,\Sigma,\delta,q_\text{start},F)$ of a DFA is given by

\[(\{q_1,q_2,q_3,q_4,q_5\},\{\texttt{d},\texttt{u}\},\delta,q_1,\{q_5\}),\]

where $\delta$ is given by the following table

\[\begin{array}{|r||c|c|} \hline & \texttt{d} & \texttt{u} \\ \hline\hline \to q_1 & q_1 & q_2 \\ q_2 & q_1 & q_3 \\ q_3 & q_2 & q_4 \\ q_4 & q_3 & q_5 \\ * q_5 & q_4 & q_5 \\ \hline \end{array}\]

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

QuestionHint

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

QuestionHint

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 string 01 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 non-accepting ones, and vice versa. This will produce a DFA that accepts strings that do not end with 01, 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

QuestionHint

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

QuestionHint

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

QuestionHint

If $\Sigma$ is an alphabet then the set of all finite-length 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

\[\Sigma^* = \Sigma^0\cup\Sigma^1\cup\Sigma^2\cup\Sigma^3\cup\Sigma^4\cup\cdots\]

For $\Sigma_1=\{\texttt{a}\}$:

Length	Strings
0	$\varepsilon$
1	$\texttt{a}$
2	$\texttt{aa}$
3	...
4	...

So,

\[\Sigma_1^* = \{ {\varepsilon}, \texttt{a}, \texttt{aa}, ..., ...,\ldots \}\]

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,

\[\Sigma_2^* = \{ {\varepsilon}, \texttt{a}, \texttt{b}, \texttt{aa}, \texttt{ab}, \ldots\ldots\ldots\ldots \}\]

Orange¶

Question 1¶

Q1 -- Set of all possible languages over an alphabet

QuestionHint

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

Theoretical constructionApplicationHint

Given two languages described by two DFAs, the idea is to construct a new DFA that simulates simultaneously-running 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

\[\begin{aligned} Q &= Q_1 \times Q_2 \\ q_0 &= (q_\text{start 1},q_\text{start 2}) \end{aligned}\]

and the transition function $\delta$ is defined by

\[\delta\Big( (p,q), \sigma \Big) = \Big( \delta_1(p,\sigma), \delta_2(q,\sigma) \Big)\]

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_1-L_2$ if

\[F=\{(p,q)\mid p\in F_1 \land q\not\in F_2\} \quad= F_1\times(Q_2-F_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_1-L_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

QuestionHint

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

\[\begin{aligned} Q_1 &= \{A\}\\\ \delta_1 &\colon (q,\sigma)\mapsto A \\ q_\text{start 1} &= A\\ F_1 &= \{A\}\\ \end{aligned}\]

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_1-L_2$. Following the result from the previous question, let

\[\begin{aligned} Q &= Q_1\times Q_2 = \{q_\text{start 1}\}\times Q_2\\ F &= F_1\times(Q_2-F_2) = \{q_\text{start 1}\}\times(Q_2-F_2) \end{aligned}\]

This means that the new DFA is essentially the DFA for $L_2$ but with the accepting and non-accepting states "flipped." (swapping roles.)

Use this observation to produce a DFA for the language

\[\{w\mid w \text{ does not contain the substring }\texttt{baba}.\}\]

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 non-accepting ones, and vice versa.

This will produce a DFA that accepts the required strings.

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`

Length	Strings
0	\({\varepsilon}\)
1	`a` `b`
2	`aa` `ab` `...` `...`
3	`aaa` `aab` `...` `...` `baa` `...` `...` `...`
4	`aaaa` `aaab` `...` `...` `...` `...` `...` `abbb`
	`baaa` `baab` `...` `...` `...` `...` `...` `bbbb`