Question

(9 pts 3 pts each) For each of the following languages, name the least powerful type of machine that will accept it, and prove your answer. (Hint: a finite state automata is less powerful than a pushdown automata, which in turn is less powerful than a Turing Machine.) For example, to prove a language needs a PDA to accept it, you would use the Pumping Lemma to show it is not regular, and then build the PDA or CFG that accepts the language. 4. a) {a'b'c' |i2 0 b) P {u|uwe L},.prefixes of L, whereL is a language over ka,b,c} and L-{w]w ends with an a e) L {a'b |i20

Answer 1

The solution is giver Here be1ow (a) give = {aibici Now we Let the sthing accoroling ahc be Pumping lemma abc Now let 2 2 abcL 2 Contemt ee during machine Now we need ala,R 8/8,R bl b,R a/a,B B B,L clC,A P-4/ywL a,b,c Laingucge ovez is a where aj ends with an L= {w/w amd turing them is enough CFR here Nou machine Kb,C

Heze given L2={a Now is emough PDA i.2 a q b b , C = b 7 according a bc to PumPing lemma man let So, it POA Now we meed turing machine 2 0,a/ q 20 O99/q 9. b,a/a bala b,a/e which is equized soluton