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

标签：

• Tokyo-University
• Chomsky-Normal-Form
• Context-Free-Grammar-Emptiness-Problem
• Context-Free-Language-Regular-Intersection
• Regular-Language-Closure-Properties

Author

kainoj, 祭音Myyura

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

题目描述

以下将 DFA 写成五元组 $\mathcal{A}=(Q,\Sigma,\delta,q_0,F)$，其中 $Q$ 是有限状态集， $\Sigma$ 是有限输入字母表，$\delta:Q\times\Sigma\to Q$ 是转移函数， $q_0$ 是初始状态，$F\subseteq Q$ 是接受状态集；将上下文无关文法写成 $G=(V,\Sigma,P,S)$，其中 $V$ 是有限非终结符集，$\Sigma$ 是有限终结符集， $P$ 是有限产生式集，$S\in V$ 是开始符号。

若文法的每条产生式均为 $B\to CD$、$B\to a$ 或 $S\to\varepsilon$，其中 $B$ 为非终结符， $C,D$ 为不同于 $S$ 的非终结符，$a$ 为终结符，则称该文法为乔姆斯基范式。 记 $\mathcal{L}(\mathcal{A})$ 为自动机接受的语言， $\mathcal{L}(G)$ 为文法生成的语言。回答下列问题。

（1）给定 DFA $\mathcal{A}=(Q,\Sigma,\delta,q_0,F)$，构造接受补语言 $\Sigma^*\setminus\mathcal{L}(\mathcal{A})$ 的 DFA。可假设 $\delta$ 为全函数。

（2）描述一个输入上下文无关文法 $G$、判定 $\mathcal{L}(G)=\varnothing$ 是否成立的算法。

（3）给定乔姆斯基范式文法 $G=(V,\Sigma,P,S)$ 和 DFA $\mathcal{A}=(Q,\Sigma,\delta,q_0,F)$，定义文法 $G_{\mathcal A}$：

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

假设 $S'$ 不属于其他形如 $B_{q,q'}$ 的非终结符。证明

$$\mathcal{L}(G_{\mathcal A}) =\bigl(\mathcal{L}(G)\cap\mathcal{L}(\mathcal A)\bigr) \setminus\{\varepsilon\}.$$

（4）给定乔姆斯基范式文法 $G$ 和 DFA $\mathcal A$，给出判定 $\mathcal{L}(G)\subseteq\mathcal{L}(\mathcal A)$ 是否成立的方法。可以使用前 三问的结论。

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(\mathcal A')$ iff $\delta^*(q_0,w)\in Q\setminus F$, which holds exactly when $w\notin\mathcal L(\mathcal A)$.

(2)

Call a nonterminal $A\in V$ generating if $A\Rightarrow^*w$ for some $w\in\Sigma^*$; otherwise it is nongenerating. The language is empty exactly when the start symbol $S$ is nongenerating.

Compute the generating symbols as follows. Initially mark every $A$ for which a production $A\to w$ has $w\in\Sigma^*$, including $w=\epsilon$. Then repeatedly mark $A$ whenever a production $A\to\alpha$ has only terminals and already marked nonterminals on its right-hand side. Stop when no new symbol can be marked.

Since $V$ is finite, this process terminates. Induction on derivation height shows that exactly the generating nonterminals are marked; hence $\mathcal L(G)=\varnothing$ iff $S$ remains unmarked.

(3)

For every $B\in V$, $p,q\in Q$, and nonempty word $w$, induction on a Chomsky-normal-form derivation gives

$$B_{p,q}\Rightarrow_{G_{\mathcal A}}^*w \iff B\Rightarrow_G^*w\ \text{and}\ \delta^*(p,w)=q.$$

The terminal-rule case follows directly from the second set of rules. In the binary-rule case $B\to CD$, split $w=uv$ according to the two subderivations and use the intermediate state $r=\delta^*(p,u)$; the converse uses the same split.

Therefore $S'\Rightarrow^*w$ iff $S\Rightarrow_G^*w$ and $\delta^*(q_0,w)\in F$. Since $G_{\mathcal A}$ has no rule generating $\epsilon$, its language is $(\mathcal L(G)\cap\mathcal L(\mathcal A))\setminus\{\epsilon\}$.

(4)

Complement $\mathcal A$ using (1), construct the grammar for

$$(\mathcal L(G)\cap\overline{\mathcal L(\mathcal A)})\setminus\{\epsilon\}$$

using (3), and test it for emptiness using (2). Also test the omitted word separately: if $S\to\epsilon$ is a rule of $G$, require $q_0\in F$. The inclusion holds iff both tests pass.