COS3701 Assignment 3 (QUALITY ANSWERS) 2025

This document contains workings, explanations and solutions to the COS3701 Assignment 3 (QUALITY ANSWERS) 2025. For assistance whats-app us on 0.6.8..8.1.2..0.9.3.4... Question 1 [10] Given that L1 = (aa)* and L2 = (a + b)*ab(a + b)*. Find grammars for L1 and L2. Then use Theorem 37 to find L1L2. Question 3 [10] Using theorem 42 algorithm to determine whether the following grammar generate any words. S AB A BC C DA B CD D a A b Look at the reformulated version of Theorem 42 in your online study units Question 4 [15] Build a Turing Machine (TM) that • accepts all words in {an bn am | n ≥ 0; m > n} • loops forever on all words starting with b, and • rejects all other words. Assume that the alphabet is Σ = {a, b} Question 5 [15] Build a 2PDA that accepts the language {a2nbnanb2n | n > 0}.