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](https://secure.expertsmind.com/CMSImages/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).