Question

(iv) {an bancam. n 20m 20) n (anamcam.n 20,m2 0) = {anbaneann 20) 4. (10%) Give a context-free grammar for the following: {a" "cºde: m +n=p+q) 5. Let the alphabet be E = {a,b,c,d,,u). Here "y" denotes a halting state of yes and "n" denotes a halting state of no. 2.1 (10%) Show the computation of the following Turing machine on Du abc 2.2 (10%) Describe in English what does this Turing machine return, given the input of u w for we {a,b,c}'.

Answer 1

please do understand my concern, as per HOMEWORKLIB RULES we are supposed to answer the first question if there is more than one question in a post, your downvote effects my career a lot, if I get a downvote for a wrong answer or incomplete answer I will accept it.

4)

The following context-free grammar produces the language

{a^mbⁿc^pd^q : m+n = p+q}

S -> aSc | aSd | bSc | bSd |

suppose we want to produce ab²c²d then

S -> aSd

-> abScd

->abbSccd

->abbccd

->abbccd