東京大学 情報理工学系研究科 コンピュータ科学専攻 2018年8月実施 専門科目I 問題3

Author

kainoj

Description

In the following, we represent a deterministic finite automaton as a quintuple \(\mathcal{A} = (Q, \Sigma, \delta, q_0, F)\) (where \(Q\) is a finite set of states, \(\Sigma\) is a finite set of input symbols, \(\delta \in Q \times \Sigma \to Q\) is the transition function, \(q_0 \in Q\) is the initial state, and \(F \subseteq Q\) is the set of final states), and a context-free grammar as a quadruple \(G = (V, \Sigma, P, S)\) (where \(V\) is a finite set of non-terminal symbols, \(\Sigma\) is a finite set of terminal symbols, \(P\) is a finite set of production rules, and \(S \in V\) is the start symbol).

A context-free grammar \(G = (V, \Sigma, P, S)\) is in Chomsky normal form if each production rule is of the form: - \(B \to CD\), - \(B \to a\), or - \(S \to \epsilon\),

where \(B\) is a non-terminal symbol, \(C\) and \(D\) are non-terminal symbols other than \(S\), \(a\) is a terminal symbol, and \(\epsilon\) is an empty sequence. We write \(\mathcal{L}(\mathcal{A})\) for the language accepted by a deterministic finite automaton \(\mathcal{A}\), and \(\mathcal{L}(G)\) for the language generated by a context-free grammar \(G\).

Answer the following questions:

(1) Let \(\mathcal{A} = (Q, \Sigma, \delta, q_0, F)\) be a deterministic finite automaton. Give a deterministic finite automaton that accepts the complement of \(\mathcal{L}(\mathcal{A})\), i.e., \(\Sigma^* \setminus \mathcal{L}(\mathcal{A})\). Here, you may assume that \(\delta \in Q \times \Sigma \to Q\) is a total function.

(2) Describe an algorithm that takes a context-free grammar \(G\) as an input, and decides whether \(L(G) = \emptyset\).

(3) Given a context-free grammar \(G = (V, \Sigma, P, S)\) in Chomsky normal form and a deterministic finite automaton \(\mathcal{A} = (Q, \Sigma, \delta, q_0, F)\), we define a context-free grammar \(G_\mathcal{A}\) as follows:

\[ \begin{aligned} V_{\mathcal{A}} &= \{ S' \} \cup \{ B_{q,q'} \mid B \in V \land (q, q') \in Q \} \\ P_{\mathcal{A}} &= \{ B_{q,q'} \to C_{q,q''} D_{q'',q'} \mid (B \to CD \in P) \land (q, q', q'' \in Q) \} \\ &\cup \{ B_{q,q'} \to a \mid (B \to a \in P) \land (q, q' \in Q) \land (\delta(q, a) = q') \} \\ &\cup \{ S' \to S_{q_0,q} \mid q \in F \}. \end{aligned} \]

Here, assume \(S' \notin \{ B_{q,q'} \mid B \in V \land (q, q') \in Q \}\). Prove that \(\mathcal{L}(G_\mathcal{A}) = (\mathcal{L}(G) \cap \mathcal{L}(\mathcal{A})) \setminus \{\epsilon\}\) holds.

(4) Give a method to decide, given a context-free grammar \(G\) in Chomsky normal form and a deterministic finite automaton \(\mathcal{A}\) as inputs, whether or not \(\mathcal{L}(G) \subseteq \mathcal{L}(\mathcal{A})\) holds. You may use the results of questions (1), (2), and (3).

Kai

(1)

Given DFA \(\mathcal{A} = (Q, \Sigma, \delta, q_0, F)\), give an automaton accepting complement of \(\mathcal{L(A)}\), i.e. \(\Sigma^*\setminus\mathcal{L(A)}\).

Let \(\mathcal{A}' = (Q, \Sigma, \delta, q_0, Q\setminus F)\) Now, \(w \in \mathcal{L(A')}\) iff \(\delta(w, q_0) \in (Q\setminus F\)) which is occurs only when \(w\notin \mathcal{L(A)}\)

(2)

Given CFG \(\mathcal{G} = (V, \Sigma, P, S)\), decide wheaterh \(\mathcal{L(G)} = \varnothing\).

We call symbol \(A\in V\) \emph{generating} if \(A\Rightarrow^* w\) for some string \(w\) of terminals. If there's no such string, then \(A\) is \emph{nongenerating}. Language of grammar \(\mathcal{G}\) is empty iff start symbol \(S\) is nongenerating. We can find set of generating symbols using the algorithm below. Symbols that are not marked generating, are nongenerating. The algorithm:

• Base. Every terminal symbol form \(T\) is generating.
• Induction. If for some production \(A\rightarrow \alpha\), \(\alpha\) is known to be generating, then is \(A\).

(3)

Looks pretty obvious from the construction. A nice induction'd make it.

(4)

If \((\mathcal{L(G)}\cap \overline{\mathcal{L(A)}}) = \varnothing\), then \(\mathcal{L(G)} \subseteq \mathcal{L(A)}\) We can compute complement based on (Q1), intersection based on (Q3) and check for emptiness based on (Q2).