代写CMPSC 464 Spring 2024 Mid Term 2 sample代写留学生数据结构程序

日期：2024-04-04 06:56

Mid Term 2 sample

CMPSC 464

Spring 2024

1 Convert CFG to PDA (10+15 points)

Consider the language L = {1nD1m |n ≤ m}

a

Construct a CFG for L

b

Convert the CFG into a PDA

2 Construct PDA (20 points)

Consider the language L over the alphabet Σ = {a,b} which contains at least twice as many a’s than b’s. Construct a PDA to recognize L.

3 Pumping lemma CFG (20 points)

Show that the language L = {ss|s ∈ Σ* } is not a context free language.

4 TM details and overview (15 + 15 points)

a

Consider the turing machine in the state xxxQ0 1111#00000#xxx1111. Essen- tially an equal number of xs are there at the beginning and post the 2nd  while there are a bunch of 0s in between the s.  Give detailed turning machine transi- tions to go to the state xxxx111#00000#xxxxP0111.  Essentially cross off the corresponding 1s with xs.

b

Give a turning machine recognizing L = {1n #0p #1n #0q #1n   |n,p,q ≥ 0}

5 Decidability andrecognizability (15+15) points

a

Consider the language which determines if the languages of two turing machines overlap INT = {< M >,< M2 > |L(M) ∩ L(M2 ) ≠ ϕ}.  Show INT is turning reconizable

b

Show INT is not decidable