Draw a TM that copy the input string in a reverse order

Assignment Help Theory of Computation

Reference no: EM133044922

Task details Answer the following questions:

Question 1. Consider the language L of all strings made of the symbols a, b that have at least length of three symbols and whose first and last symbols are different.
a. Construct an FA whose language in L.
b. Give an RE for the language in L.
c. From the RE, build a Context-Free Grammar (CFG) for L.
d. From the FA, build a regular grammar for L.

Question 2. For the language L {0,1}, find a regular expression representing the following:
a. All strings that do not begin with 11
b. All strings that every appearance of 0 is followed directly by a 1.

Question 3. Consider the following CFG with starting variable S and Σ = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0}:
S → M U V
U → N | ε
V → V V | N
N → M | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0
M → 1 | 2
a. Create a derivation tree for your student number.
b. Is this grammar ambiguous or unambiguous? Briefly explain why.
c. Convert the CFG into Chomsky Normal Form.

Question 4. Consider the following Pushdown Automaton (PDA), which recognises palindromes and where s stands for any alphanumeric symbol:

80_Pushdown Automaton.jpg

a. Explain in your own words how it recognises palindromes.
b. Would this PDA accept your first name (as printed on your student ID) as input? Explain why or why not and how it would fail or succeed.

Question 5. Draw or describe the following Touring Machines (TMs) as required:
a. Draw a TM that copy the input string in a reverse order, separating the first copy from the second copy by a special symbol for example the input string on tape is 1000, the TM should end with 1000$0001.
b. Draw a TM that compute the addition of two binary numbers, for example the input string on tape is 101$111, the TM should end with 1100
c. Describe in your own words how TM works in section b (TM that compute the addition of two binary numbers).

Reference no: EM133044922

Questions Cloud

Dissertation is methodology : An important component of your dissertation is the methodology chosen. Discuss the topic that you are selecting for your dissertation.

Bank database : What constraints do the partial key and the identifying relationship of the weak entity type specify in this diagram?

Applied cryptography in computer security : Applied Cryptography in computer security. What concept from the reading is the most applicable to you now in your profession, and how might you implement it?

Computer security-types of cryptographic methods : Classify the types of cryptographic methods that are currently in use and describe their functionality.

Draw a TM that copy the input string in a reverse order : Draw a TM that copy the input string in a reverse order, separating the first copy from the second copy by a special symbol for example the input string

Evaluate work collaboration tools : Evaluate work collaboration tools, Zoom, WebEx, and Microsoft Teams;

ERP design strategy : How might the project team recommending an ERP design strategy justify its recommendation as compared with other type of design strategies?

Rapid environmental changes on organizations : Discuss the impact of rapid environmental changes on organizations?

D21AR Advanced Design Of Reinforced Concrete Structures : D21AR Advanced Design Of Reinforced Concrete Structures Assignment Help and Solution, Heriot-Watt University - Assessment Writing Service

User Account

All Pages