Let Σ = {0, 1} and let B be the collection of strings that contain at least one 1 in their second half. In other words,B = {uv|u ∈ Σ∗, v ∈ Σ∗1Σ∗ and |u| ≥ |v|}(a) Give a Push-Down Automata (PDA) that recognises B.(b) Give a Context-Free Grammar (CFG) that recognise

(a) A Push-Down Automata (PDA) that recognises B can be constructed as follows:

States: {q0, q1, q2, q3} Input Alphabet: Σ = {0, 1} Stack Alphabet: Γ = {0, 1, $} Start State: q0 Accept State: q3 Transition Functions:

• δ(q0, ε, ε) = {(q1, )} (push onto stack and move to state q1)
• δ(q1, 0, ε) = {(q1, 0)} (push 0 onto stack for each 0 read)
• δ(q1, 1, ε) = {(q1, 1)} (push 1 onto stack for each 1 read)
• δ(q1, ε, 0) = {(q2, ε)} (on reading ε, pop 0 from stack and move to state q2)
• δ(q1, ε, 1) = {(q2, ε)} (on reading ε, pop 1 from stack and move to state q2)
• δ(q2, 0, 0) = {(q2, ε)} (pop 0 from stack for each 0 read)
• δ(q2, 1, 1) = {(q2, ε)} (pop 1 from stack for each 1 read)
• δ(q2, 1, 0) = {(q2, ε)} (pop 0 from stack for each 1 read)
• δ(q2, ε, $) = {(q3, ε)} (on reading ε, pop$ from stack and move to accept state q3)

(b) A Context-Free Grammar (CFG) that recognises B can be constructed as follows:

Variables: S, A, B Terminals: Σ = {0, 1} Start Symbol: S Production Rules:

• S → 0S | 1S | A
• A → 0A | 1A | B
• B → 1 | 1B | 0B

This CFG generates all strings that contain at least one 1 in their second half.