R04-C-問2

問2

文字列 $x$ と文字列 $y$ に対して, $\#_y(x)$ を $x$ における $y$ の部分文字列としての出現回数とする．例えば、文字列$x=abbbabb$と文字列$y=bb$について、$\#_y(x)=3$である. また、文字列$x$の反転文字列を$x^R$と表す. 以下の言語を考える:

$$\begin{align} &L_1 = \{x ∈ \{a, b\}^* | \#_a(x) = \#_b(x)\}, \\ &L_2 = \{x ∈ \{a, b\}^* | \#_{ab}(x) = \#_{ba}(x)\}, \\ &L_3 = \{x ∈ \{a, b\}^* | \#_{aa}(x) = \#_{bb}(x) = 0\}, \\ &L_4 = \{xx^R | x ∈ \{a, b\}^*\}, \\ &L_5 = \{a^i b^j c^k | i, j, k ≥ 0, j = i + k\}. \end{align}$$

言語 $L_1, L_2, L_3, L_4, L_5$ のそれぞれについて:

• 正則であれば正規表現を与えよ.
• 正則でなければ文脈自由文法を与えよ.

问题2: 语言和文法

设 $\#_y(x)$ 表示字符串 $x$ 中子字符串 $y$ 出现的次数. 例如, $\#_y(x)=3$ 表示字符串 $x=abbbabb$ 和 $y=bb$. 字符串 $x$ 的反转字符串用 $x^R$ 表示. 考虑以下语言:

$$\begin{align} &L_1 = \{x ∈ \{a, b\}^* | \#_a(x) = \#_b(x)\}, \\ &L_2 = \{x ∈ \{a, b\}^* | \#_{ab}(x) = \#_{ba}(x)\}, \\ &L_3 = \{x ∈ \{a, b\}^* | \#_{aa}(x) = \#_{bb}(x) = 0\}, \\ &L_4 = \{xx^R | x ∈ \{a, b\}^*\}, \\ &L_5 = \{a^i b^j c^k | i, j, k ≥ 0, j = i + k\}. \end{align}$$

对语言 $L_1, L_2, L_3, L_4, L_5$:

• 如果是正则语言, 请给出正则表达式.
• 如果不是正则语言, 请给出生成它的文法.