Name CSci 311: Models of Computation CSci 500: Fundamental Concepts of Computing Spring 2024 Homework #3 Direction: For each problem where you are creating a Turing Machine (TM), don't forget to write it nos a septuple as well You should create a document with ptuple with transition functions and create jff fix for actual TMx You should submit a zip file with all jf files and the document to Blackboard. For each language warme that only the symbols mentioned are in the input alphabet. 1. Using the TM below, write out the instantaneous descriptions for the following string. For each string, determine if the string is accepted or rejected by the TM after you hat the complete set of instanta descriptions. Use the symbol to represent a move from one instantaneous description the next. To get the symbol you can do the following on a Mar, type Command+Control+SpaceBar and click 'Math Symbol' in the left bar and on row 26, you should see the symbol. On a Windows machine, you should be able to hold down the ALT key and type 195' with the keypad and the symbol should show. Suggestion: Copy it once you have it and paste it when needed. (5 points each). I apologize early for the length of some of these. b; b, R 0:0, L 14. L Q;O, 0, b 1, R R b; 1, L O.L 0:0, R 1:1, R. x, R 0, R 1: 1, R L b; b, L 1: h 0; R a; a L b; b, L 1; b, R 0:0. L b;x, L 1; 1, L R Q;Q, L (%) Q; Q, R bb, R xx, L 1; 1, L 0a, 1; b, R R xx, R ta, R xx, L (a) abbbb (b) bababa xx Q;O, R R 00, R 1; 1, R. (c) ababa (d) bab (r) baabbaab 2. Using JFlip, draw a TM that accepts strings in each of the languages below. Include the septuple of the language with transition functions in the document. Asam E = {4,6} unless otherwise stated. (15 points sack). (a) L = {a*b*u*&^ 21) (b) L= {a*b*a**** : n ≥ 0,m ≥ 1} (c) = {a"""": 21,n>m) (d) £= {w: w € {a,b)+,|| mod 4 = 0} (e) = {a: € {a‚§}*, £ = {x,&,c}}/nCSci 311: Models of Computation CSci 500: Fundamental Concepts of Computing 100 points Directions: Using no line paper, answer each of the questions. Please make sure each question is labeled appropriately. You must submit the exam by Submissions must be handwritten. As indicated in the M Book, "The University is conducted on a basis of common honesty. This examination is to be completed without any direct help from any other person(s) and without the assistance from any system integrated with artificial intelligence that removes problem solving from any question. " 1. (20 points; 10 points each) Give a grammar for two of the following. Make sure to easily identify which language you selecting. Don't forget to write grammar as a quadruple, G=(...). Also if no label, then the point value assigned will be zero (0). A. L₁ = {anban: n, m≥ 1} B. L2 = {ababm: n,m≥ 1} - C. L3 = {ab: n+2m=p} D. LA {a" (bc)": n≥ 0} = 2. (80 points. 20 points each) Draw a transition graph (15 points) and provide the sextuple (5 points). You need to determine if the language requires a Turing Machine or if you can use a Nondeterministic Pushdown Acceptor to recognize strings in the language. A. L5 = {w ww, we {a,b}+} : B. L6 = {abmnm, m≥2} C. L7={abban: n, m≥ 1} D. Lg {ww" we {a,b}+} =

Fig: 1

Fig: 2