Skip to content

東京大学 情報理工学系研究科 コンピュータ科学専攻 2019年2月実施 問題3

Author

kainoj

Description

Let \(\Sigma\) be a finite alphabet (i.e., a finite set of letters). We say that a word \(v \in \Sigma^*\) is a subsequence of a word \(w = a_1 \cdots a_n \in \Sigma^*\) if \(v = a_{i_1} \cdots a_{i_2}\) for some \(k \geq 0\) and \(1 \leq i_i < \cdots < i_k \leq n\). For example, \(aab\) is a subsequence of \(acbabc\) (let \(k=3, i_1=1, i_2=4\) and \(i_3=5\)). We write \(v \preceq w\) if \(v\) is a subsequence of \(w\). Answer the following questions.

(1) Give a non-deterministic finite automaton with at most \(4\) states that accepts the language:

\[ \{w \in \{a,b,c\}^* \mid aab \preceq w\} \]

(2) Suppost that \(L \subseteq \Sigma^*\) is the language accepted by a deterministic finite automaton \(\mathcal{A} = (Q, \Sigma, \delta, q_0, F)\) (where \(Q\) is a finite set of states, \(\delta \in Q \times \Sigma \rightarrow Q\) is the transition function, \(q_0 \in Q\) is the initial state, and \(F \subseteq Q\) is the set of final states). Give a non-deterministic finite automaton that accepts the language:

\[ \{w \in \Sigma^* \mid v \preceq w \text{ for some } v \in L\} \]

(3) Supposet that \(L \subseteq \Sigma^*\) is the language accepted by a deterministic finite automaton \(\mathcal{A} = (Q, \Sigma, \delta, q_0, F)\). Assume that the transition function \(\delta \in Q \times \Sigma \rightarrow Q\) is a total function. Give a deterministic finite automaton that accepts the language:

\[ \{w \in \Sigma^* \mid v \in L \text{ for every } v \in \Sigma^* \text{ such that } v \preceq w\} \]

(4) Prove the correctness of your answer for question (3) above.

Kai

(1)

1
2
3
4
--> o --a--> o --a--> o --b--> (o)
   / \      / \      / \       / \
   \ /      \ /      \ /       \ /
    E        E        E         E

(2)

Write

\[ L_2 = \{w \in \Sigma^* | v \preceq w \text{ for some } v \in L \} \]

where \(v \preceq w\) indicates that \(v\) is subsequence of \(w\). In other words, to in order to get a word from \(L_2\), we first fix a word \(v \in L\) and then intertwine its letters with some "garbage" from \(\Sigma^*\).

Let's fix \(v\in L\). Let \(p_1, p_2, \cdots p_{|v|}\) be sequence of states that \(\mathcal{A}\) visits when reading \(v\). Label transitions between \(p_i\)'s with next letters of \(v\). Moreover, for each \(p_i\), add a loop to itself labeled with \(\Sigma\). Make \(p_1\) the start state.

(3)

First,

\[ L' = \{ w \in \Sigma^* | v\in L \text{ for every } v\in \Sigma^* \text{ such that } v\preceq w\} \]

is kinda quirky. We already supposed that \(L \subseteq \Sigma^*\), so why do we need \(v\in \Sigma^*\) above?

Let's start with constructing a NFA \(\mathcal{N}\) which accepts \(L'\). Let \(\mathcal{N}\) be a copy of \(\mathcal{A}\), where we additionally put \(\Sigma\)-labeled loops on every state. Intuitively, while traversing \(\mathcal{A}\), in every state, we can have a "detour", i.e. accept some garbage.

Having constructed NFA \(\mathcal{N}\), move to constructing equivalent DFA \(\mathcal{D}\). It is feasible, and subset construction tells us how to it. Formally, define automaton \(\mathcal{A}\) accepting \(L\) as \(\mathcal{A} = (Q, \Sigma, \delta, q_o, F)\). NFA \(\mathcal{N}\) such that \(\mathcal{L}(\mathcal{N}) = L'\) is defined as:

\[ \begin{aligned} \mathcal{N} &= (Q, \Sigma, \delta_N, q_0, F) \end{aligned} \]

where

\[ \delta_N(q, a) = \{q\} \cup \{\delta(q,a)\} \]

is a "loop" on every state. Now, equivalent DFA \(\mathcal{D}\) is obtained by subset construction:

\[ \begin{aligned} \mathcal{D} &= (Q_D, \Sigma, \delta_D, {q_0}, F_D) \\ Q_D &= \mathcal{P}(Q) \\ F_D &= \{ X\in Q_D | X\cap F \neq \emptyset\} \\ \delta_D(X,a) &= \bigcup_{q \in X} \delta_N(q,a) \end{aligned} \]

(4)

Since every DFA has equivalent NFA and vice versa, I'll prove (Q3) for NFA \(\mathcal{N}\).

Two steps:

  • \(w \in L' \Rightarrow \mathcal{N} \text{ accepts } w\).Since \(w\in L'\), then there must exits \(v\in L\) such that \(v\preceq w\).\(v\) is accepted both in \(\mathcal{A}\) and \(\mathcal{N}\), since \(\mathcal{N}\) has exactly the same states as \(\mathcal{A}\).Then, \(w\) must be accepted by \(\mathcal{N}\) by following the loops on letters of \(w\) which do not contribute to \(v\).
  • \(\mathcal{N} \text{ accepts } w \Rightarrow w \in L'\). To get \(v\) such that \(v\preceq w\), simulate \(\mathcal{N}\) on \(w\), skip the loops. Obviously \(v\in L\), because states of \(\mathcal{N}\) and \(\mathcal{A}\) are the same and \(v\) and \(w\) will end up in the same final state of \(\mathcal{N}\).