代写CMPSC 464 Spring 2024 Mid Term 2 sample代写留学生数据结构程序
- 首页 >> Python编程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