Homework answers / question archive / Theory of computation 1) Draw or describe the following Touring Machines(TMs) as required: a

Theory of computation 1) Draw or describe the following Touring Machines(TMs) as required: a

Computer Science

Share With

---

Theory of computation

1) Draw or describe the following Touring Machines(TMs) as required:

a. Draw a TM with S = {a, b} that for any input changes each a to b and each b to a. Briefly describe in your own words how it works.

b. Describe a TM that enumerates all even-length strings for a unary alphabet.

Instructions for number 1. The concept of a Turing Machine must demonstrated in detail. Diagrams should be correct, complete, and intelligible. The described Turing Machines should solve the given problems in an efficient manner, complete, and always term in ate correctly.

2) Consider the following Pushdown Automaton (PDA), which recognizes. Palindromes and where s stands for any alphanumeric symbol:

Start read s push e read e read s pop pop accept

a. Explain in your own words how it recognises palindromes.

b. Would this PDA accept the word Yhunia as input? Explain why or why not and how it would fail or succeed.

Instruction for number 2: The entire workings of a Pushdown Automaton must be explained correctly using the given examples. Processing of arbitrary strings must be explained in detail and correctly.

3) Consider the language L of all strings made of the symbols 0, 1 and 2 (S = {0, 1, 2}) that contain the sequence 012 as a substring.

a. Formally write down the alphabet of the language.

b. Give one example of a string that is constructed from the correct alphabet has a length of 6, and that is in L. Likewise, also give. One example of such a string that is not in L.

c. Construct an FA whose language is L.

d. Give a Regular Expression (RE) for L. e. From the RE, build a Context-Free Gramm ar (CFG) for L.

f. From the FA, build a regular gram mar for L.

Instructions: for number 3. Alphabet and string examples should fit the language perfectly. Finite Automaton in the Finite State Diagram, Regular Expression, and Grammars should match the language perfectly and are efficiently. Both Gram mars should be clearly Context Free and Regular, respectively, and clearly based on the Finite State Diagram.

4) Consider the following CFG with starting variable S and S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0}:

S ? M U V

U ? N | E

V ? V V I N

N ? M | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0

M ? 1 | 2

a. Create a derivation tree for 21498992.

b. is this grammar ambiguous or unambiguous? Briefly explain. Why.

c. Convert the CFG into Chomsky Norm al Form.

Instructions for number 4: The given grammar should be applied correctly and efficiently. The corresponding derivation tree must be completed and error free. All concepts of derivation trees should be correctly identified and explained in detail.