京都大学 情報学研究科 知能情報学専攻 2023年8月実施 専門科目 S-6

标签：

• 京都大学
• 上下文无关文法

Author

itsuitsuki, 祭音Myyura

Description

大学公表の原題

We consider a grammar $G = (\Sigma, N, P, S)$, where $\Sigma, N, P$, and $S$ are a finite set of terminal symbols, a finite set of nonterminal symbols, a finite set of production rules, and the start symbol, respectively.

Q.1

The following is a description on context-free grammar. Fill the blanks (1), (2), and (3).

• A grammar $G$ is a context-free grammar when, for each production rule $\alpha \rightarrow \beta$ in $P$, $\alpha \in\boxed{\qquad(1)\qquad}$ and $\beta \in\boxed{\qquad(2)\qquad}$. A language $L$ on $\boxed{\qquad(3)\qquad}$ is a context-free language when it is generated by a context-free grammar $G$.

Q.2

Prove that $L_{ab} = \{a^m b^m c^n \mid m, n > 0\}$ and $L_{bc} = \{a^m b^n c^n \mid m, n > 0\}$ are context-free languages.

Q.3

Prove that the class of context-free languages is closed under concatenation $L_1 \cdot L_2$ by constructing $G_3 = (\Sigma, N_3, P_3, S_3)$ from the context-free grammars $G_1 = (\Sigma, N_1, P_1, S_1)$ and $G_2 = (\Sigma, N_2, P_2, S_2)$ generating $L_1$ and $L_2$, respectively.

Q.4

Prove that the class of context-free languages is closed under union $L_1 \cup L_2$ by constructing $G_3 = (\Sigma, N_3, P_3, S_3)$ from the context-free grammars $G_1 = (\Sigma, N_1, P_1, S_1)$ and $G_2 = (\Sigma, N_2, P_2, S_2)$.

Q.5

$L_{abc} = \{a^k b^k c^k \mid k > 0\}$ is not a context-free language. By using this fact prove that the class of context-free languages is not closed under complement $\overline{L}$.

Q.6

Prove that the class of context-free languages is not closed under difference $L_1 - L_2$.

题目描述

考虑文法 $G=(\Sigma,N,P,S)$，分别由有限终结符集、有限非终结符集、有限产生式集和开始符号组成。

1. 填空：若每条产生式 $\alpha\to\beta$ 均满足 $\alpha\in\boxed{(1)}$、$\beta\in\boxed{(2)}$，则 $G$ 是上下文无关文法；由上下文无关文法生成的、定义在 $\boxed{(3)}$ 上的语言为上下文无关语言。
2. 证明 $L_{ab}=\{a^mb^mc^n\mid m,n>0\}$ 与 $L_{bc}=\{a^mb^nc^n\mid m,n>0\}$ 是上下文无关语言。
3. 给定生成 $L_1,L_2$ 的 CFG $G_1=(\Sigma,N_1,P_1,S_1)$、 $G_2=(\Sigma,N_2,P_2,S_2)$，构造 $G_3$ 证明 CFL 对串接 $L_1L_2$ 封闭。
4. 类似构造证明 CFL 对并集 $L_1\cup L_2$ 封闭。
5. 已知 $L_{abc}=\{a^kb^kc^k\mid k>0\}$ 不是 CFL，利用该事实证明 CFL 对补集不封闭。
6. 证明 CFL 对差集 $L_1-L_2$ 不封闭。

Kai

Q.1

(1): $N$

(2): $(N\cup \Sigma)^*$

(3): $\Sigma$ (by definition, it's not $\Sigma^*$)

Q.2

We construct a grammar that can generate all strings in a corresponding language, where all strings generated by the grammar are in the language.

For $L_{ab}$, we construct a CFG (context-free grammar)

$$G_{ab}=(\{a,b,c\},\{S,A,C\},\{S\to AC,A\to aAb,A\to ab,C\to cC,C\to c\},S)$$

and for $\forall n,m>0$, a string in the language $a^mb^mc^n$ can be generated by applying once $S\to AC$, $(m-1)$ times of $A\to aAb$, $(n-1)$ times of $C\to cC$, once $A\to ab$ and once $C\to c$ by order.

For a string generated, say $a^mb^mc^n$, it must be in $L_{ab}$ by the reversed logic above.

So $L_{ab}$ is a CFL (context-free language).

Similarly, by a CFG

$$G_{bc}=(\{a,b,c\},\{S,A,C\},\{S\to AC,A\to aA,A\to a,C\to bCc,C\to bc\},S)$$

$L_{bc}$ is generated by $G_{bc}$, thus being a CFL.

Q.3

After renaming nonterminals if necessary, assume $N_1\cap N_2=\emptyset$. Choose a new start symbol $S\notin N_1\cup N_2$ and construct the CFG

$$G=(\Sigma, N_1\cup N_2\cup\{S\},P_1\cup P_2\cup\{S\to S_1S_2\},S).$$

every generated string has a part of substrings (at left) in $L_1$ (derived from $S_1$), while the right part is in $L_2$ derived from $S_2$, forming $L_1\cdot L_2$. Every string in $L_1\cdot L_2$ can also be generated by $G$ by separating into 2 parts and finding the corresponding $P_1$ and $P_2$ rules from $S_1$ and $S_2$.

So $G$ can generate $L_1\cdot L_2$ and it is a CFL.

Q.4

After renaming nonterminals if necessary, assume $N_1\cap N_2=\emptyset$. Choose a new start symbol $S\notin N_1\cup N_2$ and construct the CFG

$$G=(\Sigma,N_1\cup N_2\cup\{S\},P_1\cup P_2\cup\{S\to S_1,S\to S_2\},S).$$

every generated string either falls in $L_1$ by applying $S\to S_1$ in the first step or falls in $L_2$ by $S\to S_2$; every string in language $L_1\cup L_2$ can find the generation rules in $P_1$ or $P_2$ plus the $S\to S_1$ or $S\to S_2$ rule.

So $G$ can generate $L_1\cup L_2$ and it is a CFL.

Q.5

Since

$$L_{abc}=L_{ab}\cap L_{bc}$$

because in RHS, the number of a's and b's must be equal and that of b's and c's are also equal, so the intersection is by definition $L_{abc}$, and $L_{abc}$ is not a CFL, if the class of CFLs are closed under complement, then for $\forall L_1,L_2$ CFL, $\overline{L_1}$ and $\overline{L_2}$ are CFLs, and $\overline{L_1}\cup \overline{L_2}$ is a CFL, and thus

$$L_1\cap L_2=\overline{\overline{L_1}\cup\overline{L_2}}$$

is a CFL (contradiction), hence under complement the class is not closed.

Q.6

Since $\Sigma^*$ is a CFL (for example, it is generated by $S\to aS$ for every $a\in\Sigma$, together with $S\to\varepsilon$), let $L$ be a CFL. If the class of CFLs were closed under difference, then $\Sigma^*-L$ would be a CFL.

However, $\overline L=\Sigma^*-L$ is by definition not necessarily a CFL because in Q.5, complement cannot make the class closed (contradiction).

So under difference the class of CFLs is not closed.