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 recognises B.

(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 states: {q3} Transition function: δ

The transition function δ is defined as follows:

1. δ(q0, ε, ε) = {(q1, )}: On empty input, push onto the stack and move to state q1.
2. δ(q1, 0, ε) = {(q1, 0)}: On input 0, push 0 onto the stack and stay in state q1.
3. δ(q1, 1, ε) = {(q1, 1)}: On input 1, push 1 onto the stack and stay in state q1.
4. δ(q1, ε, 0) = {(q2, ε)}: On empty input, pop 0 from the stack and move to state q2.
5. δ(q1, ε, 1) = {(q2, ε)}: On empty input, pop 1 from the stack and move to state q2.
6. δ(q2, 0, 0) = {(q2, ε)}: On input 0, pop 0 from the stack and stay in state q2.
7. δ(q2, 0, 1) = {(q2, ε)}: On input 0, pop 1 from the stack and stay in state q2.
8. δ(q2, 1, 0) = {(q2, ε)}: On input 1, pop 0 from the stack and stay in state q2.
9. δ(q2, 1, 1) = {(q2, ε)}: On input 1, pop 1 from the stack and stay in state q2.
10. δ(q2, ε, $) = {(q3, ε)}: On empty input, pop$ from the stack and move to 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:

1. S → 0S | 1S | A
2. A → 0A | 1A | B
3. B → 1 | 01 | 11

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