問1

状態数2の決定性有限オートマトンを考える。決定性有限オートマトン $M = (K, \Sigma, \delta, q_0, F)$ において、$K = \{q_0, q_1\}, \Sigma = \{a, b\}, F = \{q_0\}$ とする。ただし、$K, \Sigma, \delta, q_0, F$ はそれぞれ $M$ の状態集合、アルファベット、遷移関数、初期状態、最終状態の集合を表し、$a$ と $b$ は文字である。なお $\delta(p, x) = r \ (p, r \in K, x \in \Sigma)$ は、$M$ が文字 $x$ を読むことで状態 $p$ から状態 $r$ に移ることを表す。$M$ によって受理される言語を $L(M)$ で表す。 $\Sigma$ 上の正規表現 $e(a, b)$ が表す言語を $\|e(a, b)\|$ で表す。次の各問いに答えよ。

\usepackage{tikz}
\usetikzlibrary{positioning}

\begin{document}
\begin{tikzpicture}[node distance=1cm and 1cm]

  % 子图1
  \node (A1)[double, circle, draw] {$q_0$};
  \node (B1)[circle, draw] [right=of A1] {$q_1$};

  \draw[->] (A1) to[loop above] node {a} ();
  \draw[->] (A1) to node[midway, above] {b} (B1);
  \draw[->] (B1) to[loop above] node {a/b} ();

  % 子图2
  \node (A2)[double, circle, draw] [right=of B1] {$q_0$};
  \node (B2)[circle, draw] [right=of A2] {$q_1$};

  \draw[->] (A2) to[loop above] node {a} ();
  \draw[->] (A2) to[bend left] node[above] {b} (B2);
  \draw[->] (B2) to[bend left] node[below] {b} (A2);
  \draw[->] (B2) to[loop above] node {a} ();

  % 子图3
  \node (A3)[double, circle, draw] [right=of B2] {$q_0$};
  \node (B3)[circle, draw] [right=of A3] {$q_1$};

  \draw[->] (A3) to[loop above] node {a} ();
  \draw[->] (A3) to[bend left] node[midway, above] {b} (B3);
  \draw[->] (B3) to[bend left] node[midway, below] {a} (A3);
  \draw[->] (B3) to[loop above] node {b} ();

  % 子图4
  \node (A4)[double, circle, draw] [right=of B3] {$q_0$};
  \node (B4)[circle, draw] [right=of A4] {$q_1$};

  \draw[->] (A4) to[loop above] node {a} ();
  \draw[->] (A4) to[bend left] node[midway, above] {b} (B4);
  \draw[->] (B4) to[bend left] node[midway, below] {a/b} (A4);

\end{tikzpicture}
\end{document}

図1: $\delta(q_0, a) = q_0, \delta(q_0, b) = q_1$ である4種類のオートマトン $M$

1. 図1は、$\delta(q_0, a) = q_0, \delta(q_0, b) = q_1$ である4種類の $\delta$ に対応する $M$ の状態遷移図である。図1の各 $M$ について $L(M)$ に含まれる文字列を説明せよ。
2. $\delta(q_0, a) = \delta(q_0, b) = q_1$ のとき、可能な $M$ の状態遷移図を図1にならってすべて与えよ。さらに、各 $M$ について $L(M)$ に含まれる文字列を説明せよ。
3. 言語 $L = \|e(a, b)\|$ について、$\|e(b, a)\|$ を $L$ の交換言語と呼ぶ。たとえば、$L_0$ が文字 $a$ を偶数個含む文字列から構成される言語であるとき、$L_0$ の交換言語は文字 $b$ を偶数個含む文字列から構成される言語である。(1) と (2) とは異なる $\delta$ に対応する各 $M$ に対し、(1) あるいは (2) の言語の交換言語とならない $L(M)$ に含まれる文字列を説明せよ。

Q1

Consider a deterministic finite automaton with 2 states. For a deterministic finite automaton $M = (K, \Sigma, \delta, q_0, F)$, we define $K = \{q_0, q_1\}$, $\Sigma = \{a, b\}$, $F = \{q_0\}$, where $K$, $\Sigma$, $\delta$, $q_0$, and $F$ represent the set of states, the alphabet, the transition function, the initial state, and the set of final states of $M$, respectively. Here, $a$ and $b$ are characters. By $\delta(p, x) = r \ (p, r \in K, x \in \Sigma)$, we represent that $M$ reads character $x$, and transits from state $p$ to state $r$. We denote by $L(M)$ the language that is accepted by $M$.

We denote by $\|e(a, b)\|$ the language represented by a regular expression $e(a, b)$ over $\Sigma$. Answer the following questions.

\usepackage{tikz}
\usetikzlibrary{positioning}

\begin{document}
\begin{tikzpicture}[node distance=1cm and 1cm]

  % 子图1
  \node (A1)[double, circle, draw] {$q_0$};
  \node (B1)[circle, draw] [right=of A1] {$q_1$};

  \draw[->] (A1) to[loop above] node {a} ();
  \draw[->] (A1) to node[midway, above] {b} (B1);
  \draw[->] (B1) to[loop above] node {a/b} ();

  % 子图2
  \node (A2)[double, circle, draw] [right=of B1] {$q_0$};
  \node (B2)[circle, draw] [right=of A2] {$q_1$};

  \draw[->] (A2) to[loop above] node {a} ();
  \draw[->] (A2) to[bend left] node[above] {b} (B2);
  \draw[->] (B2) to[bend left] node[below] {b} (A2);
  \draw[->] (B2) to[loop above] node {a} ();

  % 子图3
  \node (A3)[double, circle, draw] [right=of B2] {$q_0$};
  \node (B3)[circle, draw] [right=of A3] {$q_1$};

  \draw[->] (A3) to[loop above] node {a} ();
  \draw[->] (A3) to[bend left] node[midway, above] {b} (B3);
  \draw[->] (B3) to[bend left] node[midway, below] {a} (A3);
  \draw[->] (B3) to[loop above] node {b} ();

  % 子图4
  \node (A4)[double, circle, draw] [right=of B3] {$q_0$};
  \node (B4)[circle, draw] [right=of A4] {$q_1$};

  \draw[->] (A4) to[loop above] node {a} ();
  \draw[->] (A4) to[bend left] node[midway, above] {b} (B4);
  \draw[->] (B4) to[bend left] node[midway, below] {a/b} (A4);

\end{tikzpicture}
\end{document}

Questions

1. Figure 1 shows four different automata $M$ such that $\delta(q_0, a) = q_0$ and $\delta(q_0, b) = q_1$. For each $M$ in Figure 1, describe the strings in the language $L(M)$.

2. Let $\delta(q_0, a) = \delta(q_0, b) = q_1$. Give the state transition diagrams of possible finite-state automata $M$ in a similar way as in Figure 1. In addition, for each $M$, describe the strings in the language $L(M)$.

3. For language $L = \|e(a, b)\|$, we call $\|e(b, a)\|$ the flipped language of $L$. For instance, let $L_0$ be the language which consists of strings that contain an even number of $a$'s. Then the flipped language of $L_0$ is the language which consists of strings that contain an even number of $b$'s. For each $M$ with $\delta$ which is different from those in (1) and (2), describe the strings in the language $L(M)$ which is not the flipped language of a language in (1) or (2).

---

中文翻译

考虑一个具有2个状态的确定性有限自动机 $M = (K, \Sigma, \delta, q_0, F)$，其中 $K = \{q_0, q_1\}, \Sigma = \{a, b\}, F = \{q_0\}$。这里，$K, \Sigma, \delta, q_0, F$ 分别表示 $M$ 的状态集合、字母表、状态转移函数、初始状态和终态集合，$a$ 和 $b$ 为字母。 $\delta(p, x) = r \ (p, r \in K, x \in \Sigma)$ 表示 $M$ 读取字母 $x$ 后，从状态 $p$ 转移到状态 $r$。自动机 $M$ 接受的语言记为 $L(M)$。 $\Sigma$ 上正则表达式 $e(a, b)$ 表示的语言记为 $\|e(a, b)\|$。

\usepackage{tikz}
\usetikzlibrary{positioning}

\begin{document}
\begin{tikzpicture}[node distance=1cm and 1cm]

  % 子图1
  \node (A1)[double, circle, draw] {$q_0$};
  \node (B1)[circle, draw] [right=of A1] {$q_1$};

  \draw[->] (A1) to[loop above] node {a} ();
  \draw[->] (A1) to node[midway, above] {b} (B1);
  \draw[->] (B1) to[loop above] node {a/b} ();

  % 子图2
  \node (A2)[double, circle, draw] [right=of B1] {$q_0$};
  \node (B2)[circle, draw] [right=of A2] {$q_1$};

  \draw[->] (A2) to[loop above] node {a} ();
  \draw[->] (A2) to[bend left] node[above] {b} (B2);
  \draw[->] (B2) to[bend left] node[below] {b} (A2);
  \draw[->] (B2) to[loop above] node {a} ();

  % 子图3
  \node (A3)[double, circle, draw] [right=of B2] {$q_0$};
  \node (B3)[circle, draw] [right=of A3] {$q_1$};

  \draw[->] (A3) to[loop above] node {a} ();
  \draw[->] (A3) to[bend left] node[midway, above] {b} (B3);
  \draw[->] (B3) to[bend left] node[midway, below] {a} (A3);
  \draw[->] (B3) to[loop above] node {b} ();

  % 子图4
  \node (A4)[double, circle, draw] [right=of B3] {$q_0$};
  \node (B4)[circle, draw] [right=of A4] {$q_1$};

  \draw[->] (A4) to[loop above] node {a} ();
  \draw[->] (A4) to[bend left] node[midway, above] {b} (B4);
  \draw[->] (B4) to[bend left] node[midway, below] {a/b} (A4);

\end{tikzpicture}
\end{document}

图 1：$\delta(q_0, a) = q_0, \delta(q_0, b) = q_1$ 的四个自动机 $M$。

回答以下问题：

1. 图1显示了4种满足 $\delta(q_0, a) = q_0, \delta(q_0, b) = q_1$ 的状态转换图。对图1中每个自动机 $M$，描述其语言 $L(M)$ 中包含的字符串。
2. 对于 $\delta(q_0, a) = \delta(q_0, b) = q_1$ 的情况，按照图1的形式列出所有可能的状态转换图，并描述每个自动机 $M$ 接受的语言 $L(M)$ 中的字符串。
3. 对语言 $L = \|e(a, b)\|$，其中$\|e(b, a)\|$称为交换语言 。例如，$L_0$ 是包含偶数个 $a$ 的字符串组成的语言，则 $L_0$ 的交换语言是包含偶数个 $b$ 的字符串组成的语言。对(1)和(2)中未覆盖的 $\delta$ 所对应的自动机 $M$，描述其语言 $L(M)$，且说明其是否属于(1)或(2)中的交换语言。

思路

1. 有限自动机通过状态转移表定义状态变化规则，第1问要求分析语言特性。
2. 第2问是更改状态转移规则，结合有限状态机的接受条件描述语言。
3. 第3问是正则表达式对应语言的变种，要求推导交换语言。

---

GPT-4o

1. 图1中的每个 $M$ 的 $L(M)$

根据图1的描述，对于每种 $M$，我们分析其语言 $L(M)$：

图1.1

状态转移：

• $q_0 \xrightarrow{a} q_0$ (停留在 $q_0$)
• $q_0 \xrightarrow{b} q_1$
• $q_1 \xrightarrow{a/b} q_1$ (停留在 $q_1$)

最终状态：$F = \{q_0\}$。
语言描述：$L(M)$ 包含所有由零个或多个字符 $a$ 构成的字符串，因为只要在 $q_0$ 读取 $a$，状态不会离开 $q_0$，读取 $b$ 则直接进入非接受状态 $q_1$。
正则表达式：$\|e(a, b)\| = a^*$。

---

图1.2

状态转移：

• $q_0 \xrightarrow{a} q_0$
• $q_0 \xrightarrow{b} q_1$
• $q_1 \xrightarrow{a} q_1$
• $q_1 \xrightarrow{b} q_0$

最终状态：$F = \{q_0\}$。
语言描述：$L(M)$ 包含所有 $b$ 的出现次数为偶数的字符串，无论是否包含 $a$，因为每次进入 $q_1$ 后必须再读取一个 $b$ 才能返回 $q_0$。
正则表达式：$\|e(a, b)\| = (a^*ba^*ba^*)^*$。

---

图1.3

状态转移：

• $q_0 \xrightarrow{a} q_0$
• $q_0 \xrightarrow{b} q_1$
• $q_1 \xrightarrow{a} q_0$
• $q_1 \xrightarrow{b} q_1$

最终状态：$F = \{q_0\}$。
语言描述：$L(M)$ 包含所有由零个或多个字符 $a$ 构成的字符串以及所有 $b$ 的出现次数为奇数的字符串，且 $b$ 必须被 $a$ 包围。
正则表达式：$\|e(a, b)\| = a^*(ba^*b)^*a^*$。

---

图1.4

状态转移：

• $q_0 \xrightarrow{a} q_0$
• $q_0 \xrightarrow{b} q_1$
• $q_1 \xrightarrow{a} q_0$
• $q_1 \xrightarrow{b} q_0$

最终状态：$F = \{q_0\}$。
语言描述：$L(M)$ 包含所有字符 $b$ 的出现次数为偶数的字符串。
正则表达式：$\|e(a, b)\| = (a^*b)^*(a^*ba^*b)^*a^*$。

---

2. $\delta(q_0, a) = \delta(q_0, b) = q_1$ 的所有可能 $M$

这种情况下，$q_0$ 是一个过渡状态，所有输入都会直接进入 $q_1$。在 $q_1$ 的状态下，根据状态转移的不同组合，可以构造以下 4 种情况：

图2.1

• $q_1 \xrightarrow{a} q_1$
• $q_1 \xrightarrow{b} q_1$

语言描述：$L(M)$ 为空，因为所有路径最终都会停在非接受状态 $q_1$。

---

图2.2

• $q_1 \xrightarrow{a} q_1$
• $q_1 \xrightarrow{b} q_0$

语言描述：$L(M)$ 包含所有 $b$ 的出现次数为奇数的字符串。
正则表达式：$\|e(a, b)\| = (a^*ba^*)^*$。

---

图2.3

• $q_1 \xrightarrow{a} q_0$
• $q_1 \xrightarrow{b} q_1$

语言描述：$L(M)$ 包含所有 $a$ 的出现次数为奇数的字符串。
正则表达式：$\|e(a, b)\| = (b^*ab^*)^*$。

---

图2.4

• $q_1 \xrightarrow{a} q_0$
• $q_1 \xrightarrow{b} q_0$

语言描述：$L(M)$ 包含所有非空字符串。
正则表达式：$\|e(a, b)\| = (a+b)^+$。

---

3. 非交换语言的分析

结合 $L(M)$ 与交换语言的定义：

• 若 $L$ 为含 $a$ 偶数个的语言，则其交换语言含 $b$ 偶数个。
• 例如，图1.2 和图1.4 中的语言 $L(M)$ 是交换的；而图1.3 中的语言不满足交换条件，因为 $b$ 的出现次数受限。

---

o1

First, let’s restate the setting for Figure 1. We have a DFA

$$M=(\{q_0,q_1\},\,\Sigma=\{a,b\},\,\delta,\,q_0,\,F=\{q_0\}),$$

where

$$\delta(q_0,a)=q_0,\quad \delta(q_0,b)=q_1.$$

What differs among the four automata in Figure 1 are the transitions from $q_1$ (on input $a$ or $b$) and which states are final. However, all four shown have $q_0$ as the (only) final state. Let us denote them $M_1, M_2, M_3, M_4$ from left to right. We want to describe the language $L(M)$ accepted by each automaton.

Below is a concise summary of each automaton, followed by an intuitive description of its language. In each diagram, an arrow labeled “$x$” from state $p$ to state $r$ indicates $\delta(p,x) = r$. A double circle indicates a final state (here always $q_0$).

---

1. The four automata in Figure 1

1.1. Automaton $M_1$

Diagram (reproducing the first one in Figure 1)

• States: $q_0$ (final), $q_1$.
• Transitions:
  • $q_0 \xrightarrow{a} q_0$ (loop on $a$),
  • $q_0 \xrightarrow{b} q_1$,
  • $q_1 \xrightarrow{a} q_1$ (loop on $a$),
  • $q_1 \xrightarrow{b} q_1$ (loop on $b$).

Since $q_0$ is final, the machine accepts exactly those strings for which, at the end of reading the input, the DFA is in $q_0$. But observe:

• As soon as we read a $b$ in state $q_0$, we move to $q_1$.
• Once we are in $q_1$, all further inputs $a$ or $b$ keep us stuck in $q_1$.
• Hence there is no path back to $q_0$.

Therefore, the only way to end in $q_0$ is never to leave $q_0$ in the first place. That means no $b$ can ever appear in the input.

Thus

$$L(M_1) \;=\; \{\,a^n : n \ge 0\,\} \;=\; a^*.$$

All strings of zero or more $a$s (and no $b$s) are accepted.

---

1.2. Automaton $M_2$

Diagram (the second one in Figure 1)

• States: $q_0$ (final), $q_1$.
• Transitions:
  • $q_0 \xrightarrow{a} q_0,\;\; q_0 \xrightarrow{b} q_1$,
  • $q_1 \xrightarrow{a} q_1,\;\; q_1 \xrightarrow{b} q_0$.

Let’s see what strings cause the DFA to end in $q_0$.

1. Reading an $a$ in $q_0$ keeps us in $q_0$.
2. Reading a $b$ in $q_0$ moves us to $q_1$.
3. Reading an $a$ in $q_1$ stays in $q_1$.
4. Reading a $b$ in $q_1$ moves us back to $q_0$.

Equivalently, the DFA flips between $q_0$ and $q_1$ only on input $b$. Every time we see a $b$, we switch states; every time we see an $a$, we remain in the same state.

• We start in $q_0$.
• If we read an even number of $b$s overall, we end up back in $q_0$.
• If we read an odd number of $b$s overall, we end in $q_1$.

Thus the machine accepts exactly those strings having an even number of $b$s (with no restriction on how many $a$s appear, or where). Formally:

$$L(M_2) \;=\; \bigl\{\, w \in \{a,b\}^* : \text{the total number of $b$s in $w$ is even}\bigr\}.$$

---

1.3. Automaton $M_3$

Diagram (the third one in Figure 1)

• States: $q_0$ (final), $q_1$.
• Transitions:
  • $q_0 \xrightarrow{a} q_0,\;\; q_0 \xrightarrow{b} q_1$,
  • $q_1 \xrightarrow{a} q_0,\;\; q_1 \xrightarrow{b} q_1$.

Now let’s track the effect of reading the last character:

• From $q_0$, reading $b$ brings us to $q_1$.
• From $q_1$, reading $b$ keeps us in $q_1$.
• From $q_1$, reading $a$ brings us back to $q_0$.
• From $q_0$, reading $a$ keeps us in $q_0$.

One very direct way to see what is accepted:

• If a string ends with $a$, then the last transition will be “$q_1 \xrightarrow{a} q_0$” (if we were in $q_1$ before) or “$q_0 \xrightarrow{a} q_0$” (if we were already in $q_0$ before). In either case, that final $a$ puts (or keeps) us in $q_0$.
• If a string ends with $b$, we must be in $q_1$ at the end (since from $q_0$ reading $b\to q_1$, or from $q_1$ reading $b\to q_1$). That is not accepted, because $q_1$ is not final.
• The empty string (no input) vacuously leaves us in $q_0$ at the end, hence accepted.

So the machine exactly accepts all strings that are either empty or end in $a$. Formally:

$$L(M_3) \;=\; \{\, w \in \{a,b\}^* : w = \epsilon \text{ or the last symbol of $w$ is }a \}.$$

---

1.4. Automaton $M_4$

Diagram (the fourth one in Figure 1)

• States: $q_0$ (final), $q_1$.
• Transitions:
  • $q_0 \xrightarrow{a} q_0,\;\; q_0 \xrightarrow{b} q_1$,
  • $q_1 \xrightarrow{a} q_0,\;\; q_1 \xrightarrow{b} q_0$.

Notice what happens from $q_1$: any input (whether $a$ or $b$) returns you to $q_0$. Equivalently:

• From $q_0$, reading $a$ stays in $q_0$.
• From $q_0$, reading $b$ jumps to $q_1$.
• Then from $q_1$, the very next character (be it $a$ or $b$) sends us back to $q_0$.

We cannot remain in $q_1$ for more than one symbol. In particular, we cannot end in $q_1$ unless the input string ends immediately after a $b$ read from $q_0$. But ending in $q_1$ is a rejection. So any time we read a $b$ from $q_0$, we must read at least one more character to get back to $q_0$.

A convenient description of $L(M_4)$ is via a regular expression:

$$L(M_4) \;=\; \bigl(a^*\bigr)\,\bigl(b(a\mid b)\,a^*\bigr)^*\!.$$

In words:

1. We can read any number of $a$s (staying in $q_0$).
2. If we read a $b$ from $q_0$, we jump to $q_1$; then the next symbol (which must exist) returns us to $q_0$. After that, again any number of $a$s is allowed, etc.

Equivalently, one cannot end the string in “$q_1$”, so one cannot have the last symbol be a “$b$” from $q_0$. But one can have arbitrarily many pairs “$b, x$” in the middle (where $x$ is $a$ or $b$), each pair returning us to $q_0$.

---

2. The case $\delta(q_0, a)=q_1$ and $\delta(q_0,b)=q_1$

Next, the problem asks us to consider all 2-state DFAs where

$$\delta(q_0,a)=q_1\quad\text{and}\quad \delta(q_0,b)=q_1,$$

i.e., from the initial state $q_0$, any input letter $a$ or $b$ causes a transition to $q_1$. As in Figure 1, we want to draw all possible ways that $\delta$ can be defined on $q_1$ (for inputs $a,b$) and decide which of $\{q_0,q_1\}$ is final. Typically, one then enumerates 2 choices (final or not final) for each state, but the question’s wording suggests “in a similar way to Figure 1” that we fix $F=\{q_0\}$ or $F=\{q_0\}\cup\{q_1\}$, etc. However, the problem statement in part (2) specifically says:

Give the state transition diagrams of possible finite-state automata $M$ in a similar way as in Figure 1. In addition, for each $M$, describe the strings in the language $L(M)$.

Usually, one interprets “similar way” to mean:

1. We keep only $q_0$ as final, or possibly only $q_1$ as final, etc.
2. We show all distinct ways to define $\delta(q_1,a)$ and $\delta(q_1,b)$.

There are 4 ways to define $\delta$ on $q_1$, since each of $\delta(q_1,a)$ and $\delta(q_1,b)$ can be either $q_0$ or $q_1$. And for each such definition, we can choose which of $\{q_0,q_1\}$ is final. Potentially that yields up to 8 diagrams—but perhaps the question wants only the 4 with “$q_0$ is final” (matching Figure 1’s style). One has to check the exact instructions or examples given in class/text.

Since the problem states: “Give the state transition diagrams … in a similar way as in Figure 1. In addition, for each $M$, describe the strings in $L(M)$.” it probably wants:

• We still have two states $\{q_0,q_1\}$.
• We keep $q_0$ as the single final state (just as in Figure 1).
• But now $\delta(q_0,a)=q_1$ and $\delta(q_0,b)=q_1$ (instead of $\delta(q_0,a)=q_0$, $\delta(q_0,b)=q_1$).
• Then we allow $\delta(q_1,a)$ and $\delta(q_1,b)$ to be either $q_0$ or $q_1$, giving 4 distinct automata.

Hence we get diagrams (call them $N_1, N_2, N_3, N_4$) analogous to $M_1, M_2, M_3, M_4$, but with the new rule at $q_0$. Let us list them explicitly. In each, $q_0$ is final.

---

Possible transitions from $q_1$

We have two binary choices:

• $\delta(q_1,a)$ = $q_0$ or $q_1$.
• $\delta(q_1,b)$ = $q_0$ or $q_1$.

So enumerating:

1. $q_1 \xrightarrow{a} q_1$, $q_1 \xrightarrow{b} q_1$.
2. $q_1 \xrightarrow{a} q_1$, $q_1 \xrightarrow{b} q_0$.
3. $q_1 \xrightarrow{a} q_0$, $q_1 \xrightarrow{b} q_1$.
4. $q_1 \xrightarrow{a} q_0$, $q_1 \xrightarrow{b} q_0$.

And in all of them:

• $q_0 \xrightarrow{a} q_1$.
• $q_0 \xrightarrow{b} q_1$.
• $q_0$ is final.

We can then describe each language $L(N_i)$ similarly to how we did in part (1). For instance:

$N_1$:

• $q_1$ loops on both $a$ and $b$.
• Once you leave $q_0$ (which happens as soon as you read any letter at all!), you get stuck in $q_1$.
• No path back to $q_0$.
  Hence the only string that leaves you in $q_0$ at the end is the empty string, $\epsilon$. So

$$L(N_1) \;=\; \{\epsilon\}.$$

$N_2$:

• $q_1 \xrightarrow{a} q_1$, $q_1 \xrightarrow{b} q_0$.

• From $q_0$, any letter puts you in $q_1$.

• Once in $q_1$, reading $a$ keeps you in $q_1$, reading $b$ sends you back to $q_0$.
  A typical acceptance pattern is that to end in $q_0$, we must read at least one $b$ at some point (because the first symbol already forces $q_0 \to q_1$). Every $a$ while in $q_1$ leaves you in $q_1$, so the only way to get back to $q_0$ is to read a $b$ in $q_1$. Concretely:

• The string cannot be empty (that would not consume any input, but the question is: do we accept $\epsilon$? Actually $\epsilon$ means “no transitions”, we stay in $q_0$, so $\epsilon$ is accepted**. Wait—be careful: If the input is empty, we do not leave $q_0$. Indeed, $\epsilon$ is accepted because $q_0$ is final and we used no transitions.

• If the string is nonempty, then after the first letter we are definitely in $q_1$. To get accepted (end in $q_0$), we must read at least one $b$ while in $q_1$. After we read that $b$, we jump back to $q_0$. Any additional letters would again pop us over to $q_1$, etc.

In short, the machine “toggles” to $q_1$ on the first symbol, then from $q_1$ you can only get back to $q_0$ by reading $b$. You can do that any number of times. One can check carefully to see if multiple toggles can happen. But an easy high-level summary is:

$$L(N_2) =\{\epsilon\}\;\cup\; \bigl\{\,w \in \{a,b\}^*:\text{the first symbol of $w$ (if any) sends $q_0\to q_1$, and then each $b$ in $q_1$ toggles you back to $q_0$, etc.}\bigr\}.$$

You can work out the precise condition (for example, strings that contain at least one $b$ if they’re nonempty, and so on). A more systematic approach:

• Start in $q_0$.
• If input is empty, accept.
• Otherwise first symbol $\to q_1$.
• We remain in $q_1$ until we read a $b$. That returns us to $q_0$.
• Then if there are more symbols, from $q_0$ we again read the next symbol and go to $q_1$, etc.

(You can continue similarly for $N_3, N_4$.)

---

3. “Flipped language” discussion

Finally, part (3) involves the notion of flipped language:

For $L=\|e(a,b)\|$, we call $\|e(b,a)\|$ the flipped language of $L$.

They give an example: “strings with an even number of $a$s” flips to “strings with an even number of $b$s.”

The question says:

For each $M$ with $\delta$ different from those in (1) or (2), describe the strings in $L(M)$ which is not the flipped language of a language in (1) or (2).

Put differently, once you exhaust the 2-state DFAs from (1) and (2), you’ll find there are still a few other 2-state DFAs possible (because you can also choose which state is final in different ways). If one of those left-over DFAs is actually the “flip” of one in (1) or (2), we don’t need to re-describe it. But if it is not just a flip of one we already covered, then we do describe it.

One typical example:

• “Strings that contain no $a$” flips to “Strings that contain no $b$.”
• “Strings with an even number of $b$” flips to “Strings with an even number of $a$.”
• “Strings ending in $a$” flips to “Strings ending in $b$.”
• etc.

Thus the question is prompting you to check all possible 2-state automata, identify which ones are “the same or the flip” of the ones already enumerated, and for any that are not flips, give the language description.

In many textbook exercises, once you list out all 2-state DFAs (with one final state, or with both states final, etc.), you notice each one’s language is either

• “all strings” or “no strings,”
• “only $a^*$,” or “only $b^*$,”
• “even number of $b$s,” “even number of $a$s,”
• “ends in $a$,” or “ends in $b$,”
• “the empty string $\{\epsilon\}$,” or “all nonempty strings,” etc.

Many of those can be matched up as flips of each other. Whichever remain unmatched are precisely the ones the question is targeting.

---

Final Answers in a Nutshell

1. Figure 1’s four automata (with $\delta(q_0,a)=q_0$, $\delta(q_0,b)=q_1$, final state $q_0$) accept:

   • $M_1$:

     $$L(M_1) \;=\; a^* \quad(\text{all strings of only $a$’s}).$$

   • $M_2$:

     $$L(M_2) \;=\;\{\,w : \text{the number of $b$’s in $w$ is even}\}.$$

   • $M_3$:

     $$L(M_3) \;=\;\{\epsilon\}\,\cup\,\{\,w\in\{a,b\}^* : \text{last symbol of $w$ is $a$}\}.$$

   • $M_4$:

     $$L(M_4) \;=\;(a^*)\bigl(b(a\mid b)\,a^*\bigr)^* \quad\text{(no string may end in a lone $b$ from $q_0$).}$$

2. All automata with $\delta(q_0,a)=q_1$ and $\delta(q_0,b)=q_1$, again splitting into 4 diagrams (depending on $\delta(q_1,a)$ and $\delta(q_1,b)$), each with $q_0$ as final. For example:

   • If $q_1$ loops on both $a$ and $b$, then $L=\{\epsilon\}$.
   • If $q_1$ goes back to $q_0$ on $b$ but loops on $a$, one gets a language of “any string where the first symbol definitely left $q_0\to q_1$, and you come back on a $b$, etc.,” plus $\epsilon$.
   • And so on for the other two possibilities.

3. Which 2-state DFAs are “new” (not a flipped version of one from (1) or (2)))? You check all possible definitions of $\delta$, plus the choice of final state(s). If it is not isomorphic to any from parts (1) or (2) nor to their “swap $a\leftrightarrow b$” version, then we describe its language. Examples might include “strings that do not contain $a$” (flip: “strings that do not contain $b$”), “all strings,” “no strings,” “the set of all nonempty strings,” etc. The question specifically asks you to:

Describe the strings in $L(M)$ (for these leftover DFAs) which is not the flipped language of a language in (1) or (2).

Hence you would just enumerate them and give a one- or two-line description analogous to the above examples.

---

Concluding Remarks

The key takeaway is that all 2-state DFAs over $\{a,b\}$ either accept a very simple “finite index” property (like “even number of $b$s”) or “no $b$” or “ends in $a$” etc. Part (3) is basically a bookkeeping exercise to show that if you try any other configuration of transitions/final-states, you get one of those old languages or you get a “flipped” version (swapping $a$ and $b$ throughout) of one of those languages. The ones that are truly “new” you must list separately.