Group 1: Holly, Dillon, Jonathan

Ambiguous grammar:

S -> aB | ab

B -> b

Ambiguous string:

ab

Derivations:

S => aB => ab

S => ab

Group: Michael Kang, Edgar Velazquez, Sandeep Isher

Problem 4: Draw a PDA capable of doing palindrome checking for string over the alphabet {a,b,c}.

Sebrianne, Gurserrat, Michael Problem 8: Define the following concepts and give an example: (a) universal Turing Machine, (b) co-r.e.-complete language, (c) co-NP complete language.

(a): U=" On input M,w, where M is a TM and w is a string: Simulate M on input w. If M ever enters its accept state, accept; if M ever enters its reject or other halt state, reject."

(b): any language that is a co re reduction. example: complement of Atm

(c): a language that is the complement of an NP complete language. have to be in co np and karp reducable. ex: complement of clocked Atm

Group 6: Nick Fulton, Prajesh Shrestha, Tyler Wasniowski Problem 5

CFLs are not closed under intersection or complementation Proof: The languages {a^(n)b^(n)c^(m)|n,m≥0} and {a^(m)b^(n)c^(n)|n,m≥0} are both context-free. Their intersection is {a^(n)b^(n)c^(n)|n≥0} which is not CFL by the pumping lemma. CFLs are not closed under complementation as using deMorgan rules, intersection can be defined from union and complementation.

Group 3: Joshua, Jinyin, Lichun

• S -> AT
• S -> c
• T -> SB
• A -> DD
• B -> b
• D -> a
• "aacb"

! CYK Algorithm |-

• First see which variables are already present in the symbol table, in this case, a is present in D, c is present in S and b is present in B. So populate these cells just above the values.
• Next, couple together neighboring symbols like 'aa' 'ac' and 'cb' to see if the combination of the terminals in their cells are present in the symbol table. In this case, 'aa' (DD) is present in 'A' and 'cb' (SB) is present in 'T'. Populate the appropriate cells.
• Next as you keep comparing each combination of terminals, the only comparison that will bring a result is combining {A} and {T}, which is present in "S". Since it is present in "S", the string is accepted with this grammar.

Group 2: Sartaj Singh, Keven Lam

1. Sumaiyya Burney, Jiajian Liu, and Zhijie Xu

A pushdown automaton with 2 stacks is a 7-tuple M=(Q,Σ,Γ,δ,q0,z,F) where:

Q is the set of states,

Σ is the input alphabet,

Γ is the first stack alphabet

δ:Q×(Σ∪{ε})×(Γ∪{ε})×(Γ∪{ε})→P(Q×(Γ∪{ε}xΓ∪{ε})) is the transition function

q0∈Q is the start state,

z1z2∈Γ is the start of stacks symbol.

F⊆Q is the set of accept states.

Show this model can simulate a Turing Machine and that a Turing Machine can simulate a two stack PDA.

A Turing machine can move left and right with the tape head always in the middle of whats to its left and to its right. This can be emulated by a PDA and vice versa by imagining each half of the input tape as a stack. Let everything that is to the left be one stack and everything to the right be another stack. To move left, pop the left stack and push to the right one. To move right, pop from the right stack and push to the left.

Group 1: Holly, Dillon, Jonathan

Problem 10:

Let ASCII154 be the set of strings written in ASCII as Professor Pollett would call solutions to this problem. Let B = { <M> | L(M) = ASCII154 }. B satisfies the two required conditions necessary for proving undecidability via Rice's therorem. First, it is nontrivial because some TMs have languages that accept strings that are not answers to this problem while other TMs do not. Second, it depends only on the language. If two TMs recognize the same language, either both have descriptions in B or neither do. Consequently, Rice's theorem implies that B is undecidable.

Sebrianne, Gurseerat, Michael

'''Q9 Define computation history.''' Let M be a TM and x an input string.

An accepting computation history for M on x is a sequence of configurations C1,...,Ck, where C1 is the start configuration of M on x, Ck is an accepting configuration of M, and each Ci legally follows from Ci−1 according to the rules of M.

A rejecting computation history for M is defined similarly, except that Ck is a rejecting configuration.

''' Prove ELBA is undecidable using a computation history argument.''' The reduction is from ATM. We show if ELBA is decidable then ATM also would be decidable. Suppose R is decision procedure for ELBA. Let L={w|w is a string of the form C1#C2#Ck giving a legal accepting computation history of M on input x}. One can show that L can be recognized by an LBA; let's call it B. Further, if L is empty, M,x is not in ATM. So if ELBA were decidable the following would be a decision procedure for ATM: S= "On input M,x, where M is a TM and x is a string:

1. Construct LBA B from M on x .
2. Run R on input B.
3. If R rejects, accept; if R accepts, reject." Q.E.D.

In fact, ELBA is Turing-complete for co-r.e. for essentially the same reasons as ETM was.