オートマトン (2)
本問を選択(Select this problem){ する(Yes)，しない(No) } No.
(1) 次の文法Gにより生成される言語をL1とする．
S →²|a|b|aSa|bSb
ここで，Sは開始記号および非終端記号であり，aとbとは終端記号である．
文法Gにより ababaが導出される過程を示しなさい．
Let L1 be the language generated by the following grammar G:
S →²|a|b|aSa|bSb
where the start symbol is S that is also the nonterminal, and the terminals areaand b.
Show a derivation of abababy G.
(2) 言語L2を次のように定義する．
L2 ={w∈ {a,b}∗ |w=wR}
ただし，wの逆をwRで表す．すなわち，(xnxn−1. . . x1)R=x1x2. . . xnであり，²R=²である．
長さが5以上のw∈L2を一つ示しなさい．
Let L2={w∈ {a,b}∗ |w=wR}, where wR is the reversal ofw, that is, (xnxn−1. . . x1)R=x1x2. . . xn and ²R=².
Show one exmaple w∈L2 such that the length ofwis greater than 4.
(3) L2⊆L1が成立することを証明しなさい．
Prove that L2 ⊆L1. (4) L1⊆L2を証明しなさい．
Prove that L1 ⊆L2.
(解答は裏面を使用しても構わない．You can use the reverse side of this paper for your answering.)
