CS341 Automata TheoryHomework Assignment ♯5Do not forget to write your name and EID.1. Consider t his CFG G:S → D|ED → dD|dDe|dFE → Ec|dEe|F eF → ε(a) Give a concise definition of L(G).(b) Show the leftmost derivation of string ddeee in L(G).(c) Rewrite G in Chomsky Normal Form. Use the algorithm given in class, and showeach step.2. Define a PDA that recognizes L = {ambn|m, n ≥ 0, n = 3m or n = 2m}.3. Define a CFG that generates L = {w ∈ {0, 1}∗|w contains at least as many 0 s as 1s}.4. For each language indicate whether the language is (I) regular, (II) context-free but notregular, (III) semi-decidable but not context-fr ee. Prove your answer. For these lan-guages, if you choose (III), draw a state diagram of the Turing machine that recognizesthe language (instead of giving an English description of the TM).(a) L = {w ∈ {a, b}∗|#0(w) = #1(w), and at any point in string w, there are notmore 1s than 0s before that point}(b) L = {a3kb2kck|k ≥ 0}5. Indicate whether each of t he following statements are true or false, and prove youranswer.(a) If L1, L2, L3, ... are context-free languages, then L =SLiis context-free.(b) If L1, L2are languages such that L1∩L2is regular, then L1and L2are context-free.6. (a) Design a Turing machine M that recognizes {02n|n ≥ 0}.(b) Give the sequence of configurations that M enters when started on the indicatedinput string:i. 0ii. 00007. Examine the formal definition of a Turing machine that we gave in class t o answer thefollowing questions, and explain your reasoning.1(a) Can a TM ever write the blank symbol on its tape?(b) Can the tape alphabet be the same as the input alphabet?(c) Can a TM’s read head ever be in the same location before and after a transition?(d) Can a TM have only one state?8. Give state diagrams for TMs that recognize the following languages:(a) {w ∈ {0, 1}∗|w contains twice a s many 0s as 1s}(b) {0k10k10k|k ≥ 0} (Define a decider for this
View Full Document
Unlocking...