IS CS-2019S1-03

题目来源：Problem 3 日期：2024-08-02 题目主题: CS-Formal Languages-Automata and Grammars

Solution

Question 1: Complement of a DFA Language

To construct a deterministic finite automaton (DFA) that accepts the complement of $L(\mathcal{A})$, we can use the following step:

Flip the Final States: Let $\mathcal{A}=(Q,\Sigma ,\delta ,q_0,F)$ be the given DFA. The complement DFA, denoted as ${\mathcal{A}}^c$, will have the same set of states $Q$, the same alphabet $\Sigma$, the same transition function $\delta$, and the same initial state $q_0$. The set of final states $F^c$ in ${\mathcal{A}}^c$ will be $Q\setminus F$. This means that all non-final states in $\mathcal{A}$ become final states in ${\mathcal{A}}^c$, and all final states in $\mathcal{A}$ become non-final states in ${\mathcal{A}}^c$.

Formally, the complement DFA ${\mathcal{A}}^c$ is given by:

$${\mathcal{A}}^c=(Q,\Sigma ,\delta ,q_0,F^c)$$

where $F^c=Q\setminus F$.

This works because:

• For any string $w\in {\Sigma }^{\ast }$, $\mathcal{A}$ and ${\mathcal{A}}^c$ will end up in the same state after reading $w$.
• If $w\in L(\mathcal{A})$, $\mathcal{A}$ ends in a final state, so ${\mathcal{A}}^c$ ends in a non-final state, rejecting $w$.
• If $w\notin L(\mathcal{A})$, $\mathcal{A}$ ends in a non-final state, so ${\mathcal{A}}^c$ ends in a final state, accepting $w$.

Question 2: Deciding if $L(G)=\varnothing$

We can use the following algorithm to decide whether $L(G)=\varnothing$:

1. Mark the start symbol $S$ as “reachable”.
2. Repeat until no new non-terminal symbols are marked:
   • For each production rule $A\to \alpha$ where $A$ is marked:
     • Mark all non-terminals in $\alpha$ as “reachable”.
3. If any marked non-terminal has a production rule that produces only terminals, return ”$L(G)$ is not empty”.
4. Otherwise, return ”$L(G)$ is empty”.

This algorithm works because:

• It finds all non-terminals that can be derived from the start symbol.
• If any of these can produce a string of terminals, the language is non-empty.
• If none can produce a string of terminals, the language is empty. Since:
  1. The set of non-terminals in the grammar is finite.
  2. In each step, we either mark new non-terminals as reachable or terminate the algorithm.
  3. We can mark at most all non-terminals, which is bounded by the size of the non-terminal set.

Time complexity: $O(|V|+|P|)$, where $|V|$ is the number of non-terminals and $|P|$ is the number of production rules.

Question 3: Proving $L(G_{\mathcal{A}})=(L(G)\cap L(\mathcal{A}))\setminus \{ϵ\}$

To prove that $L(G_{\mathcal{A}})=(L(G)\cap L(\mathcal{A}))\setminus \{ϵ\}$, we follow these steps:

1. Generating Strings in $L(G_{\mathcal{A}})$: The non-terminal $B_{q,q^{\prime }}$ in $G_{\mathcal{A}}$ generates strings that, according to $G$, can derive terminal symbols that transform the DFA $\mathcal{A}$ from state $q$ to state $q^{\prime }$. Specifically:

   • The production $B_{q,q^{\prime }}\to a$ exists if $B\to a\in P$ and $\delta (q,a)=q^{\prime }$, which means $a$ takes the DFA from $q$ to $q^{\prime }$.
   • The production $B_{q,q^{\prime }}\to C_{q,q^{\prime \prime }}{D}_{q^{\prime \prime },q^{\prime }}$ corresponds to a sequence of non-terminals $C$ and $D$ generating a string that leads the DFA through states $q\to q^{\prime \prime }\to q^{\prime }$.

2. Intersection of $L(G)$ and $L(\mathcal{A})$:

   1. $L(G_{\mathcal{A}})\subseteq L(G)$ Every production in $G_{\mathcal{A}}$ corresponds to a production in $G$. Specifically:

      • $B_{q,q^{\prime }}\to C_{q,q^{\prime \prime }}{D}_{q^{\prime \prime },q^{\prime }}$ in $G_{\mathcal{A}}$ corresponds to $B\to CD$ in $G$.
      • $B_{q,q^{\prime }}\to a$ in $G_{\mathcal{A}}$ corresponds to $B\to a$ in $G$. Therefore, any string generated by $G_{\mathcal{A}}$ can also be generated by $G$ using the corresponding productions. This ensures that $L(G_{\mathcal{A}})\subseteq L(G)$.

   2. $L(G_{\mathcal{A}})\subseteq L(\mathcal{A})$ The construction of $G_{\mathcal{A}}$ incorporates the state transitions of $\mathcal{A}$:

      • The start production $S^{\prime }\to S_{q_0,q}$ where $q\in F$ ensures that generated strings start from the initial state $q_0$ and end in a final state $q$.
      • Productions $B_{q,q^{\prime }}\to C_{q,q^{\prime \prime }}{D}_{q^{\prime \prime },q^{\prime }}$ maintain valid state transitions in $\mathcal{A}$.
      • Terminal productions $B_{q,q^{\prime }}\to a$ are only included when $\delta (q,a)=q^{\prime }$ in $\mathcal{A}$. These constraints guarantee that any string generated by $G_{\mathcal{A}}$ is accepted by $\mathcal{A}$, thus $L(G_{\mathcal{A}})\subseteq L(\mathcal{A})$.

   3. Exclusion of $ϵ$:

      1. $G$ is in Chomsky Normal Form (CNF), which only allows $ϵ$ production as $S\to ϵ$, where $S$ is the start symbol.
      2. In the construction of $G_{\mathcal{A}}$, we explicitly exclude this $ϵ$ production. The new start symbol $S^{\prime }$ only has productions of the form $S^{\prime }\to S_{q_0,q}$, which always lead to non-empty strings. Therefore, $ϵ\notin L(G_{\mathcal{A}})$, and we can conclude that $L(G_{\mathcal{A}})\subseteq (L(G)\cap L(\mathcal{A}))\setminus \{ϵ\}$.

Therefore, $L(G_{\mathcal{A}})=(L(G)\cap L(\mathcal{A}))\setminus \{ϵ\}$.

Question 4: Deciding if $L(G)\subseteq L(\mathcal{A})$

To decide whether $L(G)\subseteq L(\mathcal{A})$, we can proceed as follows:

1. Compute $L({\mathcal{A}}^c)$: Construct the DFA ${\mathcal{A}}^c$ that accepts the complement of $L(\mathcal{A})$.

2. Intersect $L(G)$ with $L({\mathcal{A}}^c)$: Construct a context-free grammar $G_{{\mathcal{A}}^c}$ as described in question 3. This grammar generates the language $(L(G)\cap L({\mathcal{A}}^c))\setminus \{ϵ\}$.

3. Check if $L(G_{{\mathcal{A}}^c})$ is Empty: Using the algorithm from question 2, determine whether $L(G_{{\mathcal{A}}^c})=\varnothing$. If $L(G_{{\mathcal{A}}^c})=\varnothing$, then $L(G)\cap L({\mathcal{A}}^c)=\varnothing$, implying that $L(G)\subseteq L(\mathcal{A})$. Otherwise, $L(G)⊈L(\mathcal{A})$.

知识点

DFA上下文无关语言乔姆斯基范式算法补语言

重点词汇

• DFA (Deterministic Finite Automaton): 确定有限自动机
• Context-Free Grammar: 上下文无关文法
• Chomsky Normal Form: 乔姆斯基范式
• Complement: 补集

参考资料

1. Introduction to the Theory of Computation by Michael Sipser, Chapter 2 and 4.