Description

CENG280
Formal Languages and Abstract Machines
Take Home Exam 3

Objectives
To familiarize with computation using Turing Machines and inspect aspects of language hierarchy covered throughout the course.
Specifications
You must adhere to the notation conventions adopted in the textbook. Use the standard deterministic Turing Machine as defined in the book unless stated otherwise. You should utilize basic machines notation for the fifth question.
Your solution should be delivered as a .tex file based on your modification of the provided template file.
Questions and submission regulations are included in subsequent sections. Designing your solutions to the tasks, explicitly state any assumptions you make and pay particular attention to the notation you use. Your proofs must be sound and complete. Grading will be heavily affected by the formalization of your solutions.
Question 1 (10 pts)
Given the context-free grammmar G = (V,Σ,R,S) where V = {S,X,a,b,c} and Σ = {a,b,c} and
R = {S → aSXaX, S → bSXbX, S → c, X → aX, X → bX, X → e}
a. Construct a bottom-up parser for G.
b. Trace w = abbcbabbaa using yields-in-one-step relation on successive configurations of the parser you defined in (a).
Question 2 (15 pts)
In each part, give a formal description for the Turing machines that computes the given function.
( x + 1 if x is odd
a. f(x) =, where x ≥ 1.
if x is even
b. g(x,y) = |x − y|, where x,y ≥ 1. (ungraded)
Numbers will be given to TM’s in unary. Initially, in part (a), tape is of the form (.t11…11t t …) where number of 1’s equal to x, and in part (b), (.t11…1111…11t t …), where number of 1’s before the square symbol represent x and number of 1’s after the square symbol represent y. For both parts, initial position of the head is the blank symbol which is between left end symbol and the input. When the machines halt, tape will be of the form (.t11…11t t …) where number of 1’s equal to the output of the function. Final position of the head does not matter.
In your description, represent the TM’s as quintuples (K, Σ, δ, s, H) where K is the finite set of states; Σ is the alphabet containing blank symbol t, input separator symbol (for part (b)), left end symbol , and any other symbol you need to compute the functions, but not containing symbols → and ←; δ is the transition function from (K-H)×Σ to K×Σ × {→,←}; s is the start state and H is the set of halting states.
Question 3 (10 pts)
Question 4 (25 pts)
Queue-based deterministic Turing Machines utilize a semi-infinite tape allowing only the following operations:
• front: access the first element of the input string on tape
• rear: access the last element of the input string on tape assuming that the rest of the tape is filled with blank symbols
• enqueue: append a new element to the end of the queue which becomes the rear element
• dequeue: remove the first element of the queue and update the front element accordingly.
Let queue-based TM have effectively two heads pointing to front and rear positions, and other than enqueue / dequeue operations it is not allowed to move heads left or right.
a. Formally define the queue-based TM using tuple notation. State the type of each constituent of the tuple.
b. Formally define the notion of configuration for the queue-based TM.
c. Assume that the front and rear heads initially point to the beginning and end of input string of the queue-based TM. Formally define the yields-in-one-step relation of the machine. Write in set notation the language recognized by the reflexive transitive closure of yields-in-one-step relation.
d. Prove that queue-based deterministic TM is equivalent to the standard TM.
e. Formally define a queue-based TM to decide the language L = {wcw : w ∈ {a,b}∗}.
Question 5 (20 pts)
Given the language L = {anb2nc3n : n ∈ N} (Note that strings in L can be enumerated as
{b,abbccc,aabbbbcccccc,aaabbbbbbbbccccccccc,…}),
a. Use basic machines notation to provide a deterministic TM that decides L.
b. Formally define a grammar that generates only all the strings in L.
Question 6 (20 pts)
You are given the following information about formal languages L1, L2, L3, L4, and L5, all defined over alphabet Σ = {a,b}:
• A regular grammar can generate all strings in L1 and nothing else.
• A deterministic top-down parser can be built for context-free grammar whose language is L2.
• Only an inherently ambiguous context-free grammar can be provided for L3.

• There is a TM M that decides L4 ∩ L(a∗b∗).
• An unrestricted grammar can generate all strings in L5.
Let
a. Do TM’s M1, M2, M2, M3, M4 and M5 that accept L1, L2, L3, L4, and L5 respectively exist?
b. Are there always algorithms for membership problems associated with each of L1, L2, L3, L4, and L5?
c. Show precisely how to accept a string in L by using abstract machines constructed for L1, L2, L3,
L4, and L5.

d. Can we always come up with a TM that semidecides L? Justify your answer.
Question 7 (ungraded)
Prove that L is not recursively enumerable where
L = {”M””w” : ”M” is encoding of a Turing machine and w 6∈ L(M)}.
Submission
• You should submit your THE1 as a .tex file. Please use the template provided on COW with appropriate modifications.
• Do not submit solutions for not-graded questions. Yet solving them is advisable in studying for the midterm.
Regulations
2. Newsgroup: You must follow the newsgroup (news.ceng.metu.edu.tr) for discussions and possible updates on a daily basis.