"If I had more time, I would have written a shorter letter" is a quote from French mathematician and philosopher Blaise Pascal in his 1657 Lettres Provinciales. Summarize your reflection paper in a 50- to 60-word abstract. Describe the differences between the computational complexity of classes P and NP. What is the Halting Problem? If the Halting Problem were solvable, describe in detail the technological and societal implications. All six (6) of the following statements are false. Choose three (3) of the six (6) statements below and show that they are false by either using a counterexample, or citing a theorem or an established fact. For example, both O and (e) are known to be context free. 1. If L is context free and L2 is not context free, then L L2 is NOT context free. 2. If L is context free and L is not context free, then L L is context free. 3. Every context free language is not regular. 4. If L is context free and L is not context free, then L L is NOT context free. 5. A non-deterministic Turing Machine can decide languages that standard Turing Machine cannot decide. 6. There are languages that are decided by a Turing Machine with two (2) tapes, but is undecidable by a Turing Machine with one (1) tape. For the following Turing Machine carry out the computations, starting with configuration (s, Duabu). (Note: R2 means RR). U Note in the diagram below that a is a variable that can store a, b, or L. >Lu R Ru au Rala 2 Complete the seven (7) remaining transitions represented by 6 for Turing Machine M that scans to the right until it finds two (2) consecutive b's then halts. (Note: be careful on this. Look for two consecutive b's and NOT just a second b.) M = (S, E, S, s. (h}) S = {s, q, h} [= {4, D. a, b} 8= First transition = ((s, b), (q, )) Second transition Third transition Fourth transition Fifth transition Sixth transition Seventh transition Eighth transition For the Pushdown Automaton M = {Q, E, I, s, 8, F), where Q = {s, f} = {a, b}, F = {f} r = {a} 8= {((s,a,e), (s,a)), ((s,b,e), (s,a)), ((s,a,e), (f.e)), ((f,a,a), (f,e)), ((f,b,a), (f.e))} Determine if each of the following strings is in L(M) by creating a table with columns as listed below for (1) state s or f, (2) remaining input string, and (3) stack values. 1. baa 2. aba state input left stack Let G be the regular context-free grammar (, NT, R, S), where = {a,b), NT = {A,B,S) and R = {SabA, SB, S baB, Se, AbS, BaS, A b} Trace the transitions that lead to the acceptance of the string aabbabbabb by L(G). For language LC (a, b)* find a regular expression representing each of the following: 1. L= {all strings with NO occurrence of ab} 2. L = {all strings that do not begin with ab nor end with ba} Use the Pumping Lemma to show the following language L is NOT regular. L={w E (a, b, c)*; where w has equal number of a's, b's, and c's} Use the Pumping Lemma to show the following language L is NOT regular. L={w E (a, b, c)*; where w has equal number of a's, b's, and c's}