Given the PDA 𝑀 = ({𝑞1, 𝑞2}, {0, 1}, {#, 𝐵, 𝐺}, Δ, 𝑞1, #, ∅) (empty-cell
Posted: Thu Jun 02, 2022 8:32 am
Given the PDA 𝑀 = ({𝑞1, 𝑞2}, {0, 1}, {#, 𝐵, 𝐺}, Δ, 𝑞1, #, ∅)
(empty-cell acceptors) with the following transition table for
Δ:
Let 𝑤 = 001100 ∈ 𝐿(𝑀). A configuration sequence of 𝑀 that
recognizes 𝑤 is: (𝑞1, 001100, #) → (𝑞1, 01100, 𝐵#) → (𝑞1, 1100,
𝐵𝐵#) → (𝑞1, 100, 𝐺𝐵𝐵#) →(𝑞2, 00, 𝐵𝐵#)
→ (𝑞2, 0, 𝐵#) → (𝑞2, 𝜀, #) → (𝑞2, 𝜀, 𝜀) → accepted
Find two other configuration sequences (not necessarily
accepting)
Describe the language that 𝑀 accepts.
Find a grammar that generates this language.
A(91,0, #) = {(9₁, B#} A(9₁,1, #) = {(91, G#} A(91,0, B) = {(91, BB), (92, €)} A(91, 0, G) = {(9₁, BG)} A(91,1,B) = {(q1, GB)) A(91,1,G) = {(9₁, GG), (92, €)} A(92,0, B) = {(92, €)} A(92,1,G) = {(92, €)} A(q₁, E, #) = {(92, ε)} A(92, E, #) = {(92, €)}
(empty-cell acceptors) with the following transition table for
Δ:
- 1 (15.96 KiB) Viewed 13 times
recognizes 𝑤 is: (𝑞1, 001100, #) → (𝑞1, 01100, 𝐵#) → (𝑞1, 1100,
𝐵𝐵#) → (𝑞1, 100, 𝐺𝐵𝐵#) →(𝑞2, 00, 𝐵𝐵#)
→ (𝑞2, 0, 𝐵#) → (𝑞2, 𝜀, #) → (𝑞2, 𝜀, 𝜀) → accepted
Find two other configuration sequences (not necessarily
accepting)
Describe the language that 𝑀 accepts.
Find a grammar that generates this language.
A(91,0, #) = {(9₁, B#} A(9₁,1, #) = {(91, G#} A(91,0, B) = {(91, BB), (92, €)} A(91, 0, G) = {(9₁, BG)} A(91,1,B) = {(q1, GB)) A(91,1,G) = {(9₁, GG), (92, €)} A(92,0, B) = {(92, €)} A(92,1,G) = {(92, €)} A(q₁, E, #) = {(92, ε)} A(92, E, #) = {(92, €)}