オートマトン・形式言語演習問題解答例

オートマトン・形式言語演習問題解答例
2014 年 12 月 23 日分
1. (a) 属する． S ⇒ Sa ⇒ Saa ⇒ baa
(b) 属さない．
(c) 属する．S ⇒ S0 ⇒ S1S0 ⇒ S1a0 ⇒ S1S1a0 ⇒ a1S1a0 ⇒ a1b1a0
2. (a) 最左導出: S ⇒ A1B ⇒ 0A1B ⇒ 00A1B ⇒ 001B ⇒ 0010B ⇒ 00101B ⇒ 00101
最右導出: S ⇒ A1B ⇒ A10B ⇒ A101B ⇒ A101 ⇒ 0A101 ⇒ 00A101 ⇒ 00101
(b) 最左導出: S ⇒ A1B ⇒ 1B ⇒ 10B ⇒ 100B ⇒ 1001B ⇒ 1001
最右導出: S ⇒ A1B ⇒ A10B ⇒ A100B ⇒ A1001B ⇒ A1001 ⇒ 1001
3. (a) G = ({S}, {0, 1}, P, S)
P = { S → 0S1 | 01
(d) G = ({S}, {0, 1}, P, S)
P = { S → 0S0 | 1S1 | ε }
}
(b) G = ({S}, {0, 1}, P, S)
P = { S → 0S1 | 0S | 0 }
(e) G = ({S}, {0, 1}, P, S)
P = { S → 0S1S | 1S0S | ε }
もしくは，
(c) G = ({S, A, B}, {0, 1}, P, S)
P = { S → A | B,
→
→
A
B
P ={
0A1 | 0A | 0,
0B1 | B1 | 1 }
4. (a) G = ({S, A}, {0, 1}, P, S)
P ={ S
A
→ 0S | 1A,
→ 0A | 1A | ε
}
(b) 1
1
S
A
B
0
1
0
S
→
0S1 | 1S0 | SS | ε
}

Download Report