R04-C-問2

問2

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

$$\begin{array}{rl}& L_1=\{x\in \{a,b{\}}^{\ast }|{\#}_a(x)={\#}_b(x)\},\\ & L_2=\{x\in \{a,b{\}}^{\ast }|{\#}_{ab}(x)={\#}_{ba}(x)\},\\ & L_3=\{x\in \{a,b{\}}^{\ast }|{\#}_{aa}(x)={\#}_{bb}(x)=0\},\\ & L_4=\{x{x}^R|x\in \{a,b{\}}^{\ast }\},\\ & L_5=\{a^i{b}^j{c}^k|i,j,k\ge 0,j=i+k\}.\end{array}$$

言語 $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{array}{rl}& L_1=\{x\in \{a,b{\}}^{\ast }|{\#}_a(x)={\#}_b(x)\},\\ & L_2=\{x\in \{a,b{\}}^{\ast }|{\#}_{ab}(x)={\#}_{ba}(x)\},\\ & L_3=\{x\in \{a,b{\}}^{\ast }|{\#}_{aa}(x)={\#}_{bb}(x)=0\},\\ & L_4=\{x{x}^R|x\in \{a,b{\}}^{\ast }\},\\ & L_5=\{a^i{b}^j{c}^k|i,j,k\ge 0,j=i+k\}.\end{array}$$

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

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