Reference no: EM132896654

COMP 3722 Theory and Practice of Computing - Flinders University

1. Finite State Automata and Regular Languages

Use the construction given in the lecture handouts (and also in Theorem 1.45 of Sipser) to give the state diagram for a nondeterministic finite-state automaton that recognizes the union of the following two languages over the alphabet {0, 1}:

a. {w | every pair of 0's in w has at least one 1 between them}
b. {w | the symbol in every odd position of w is a 1}

2. Pumping Lemma ( answer either Part A or Part B)

Part A: Regular Languages (answer either this part or Part B)

Let Σ = {0, 1, +, = } and ADD = {x=y+z | x, y, z are binary integers, and x is the sum of y and z}.
For example, 110=101+1 is in ADD.
Use the pumping lemma for regular languages to show that ADD is not regular.

Hint: It may be helpful to choose s = 1^p=0+1^p.

Part B: Context-free Languages (answer either this part or Part A)

Let Σ = {1, 2, 3, 4} and C = {w ∈ Σ* | the number of 1s in w equals the number of 2s, and the number of 3s in w equals the number of 4s}.

For example, 14332124 is in C.
Use the pumping lemma for context-free languages to show that C is not context-free.

Hint: It may be helpful to choose s = 1^p3^p2^p4^p.

3. Decidability

A string s is a proper prefix of a string t if t starts with s but is not equal to s (i.e. t is equal to s followed by one or more additional symbols). A language is prefix-free if it does not contain any string that is a proper prefix of any other string in the language. Let PREFIX-FREE_REX = {R | R is a regular expression where L(R) is prefix-free}.

Show that PREFIX-FREEREX is decidable.

You may use (without proof) the fact that regular languages are closed under the operations of
• Star
• Concatenation
• Union
• Intersection
• Complement

and that each of the following languages is decidable:
• A_DFA = {<D, w> | D is a DFA and D accepts w}
• A_NFA = {<N, w> | N is a NFA and N accepts w}
• A_PDA = {<P, w> | P is a PDA and P accepts w}
• A_REX = {<R, w> | R is a regular expression and R generates w}
• E_DFA = {<D> | D is a DFA and L(D) = Ø}
• E_QDFA = {<D, E> | D and E are DFAs and L(D) = L(E)}
• A_CFG = {<G, w> | A is a CFG and A generates w}
• E_CFG = {<G, w> | E is a CFG and L(E) = Ø }
• any regular language
• any context-free language.

Hint: Given a particular regular expression R over the alphabet Σ, construct a regular expression R′ for: the language of all strings that consist of a string from L(R) followed by some additional symbols. The language L(R′) is the language of all strings that have some string from L(R) as a prefix. Consider what relationship should hold between L(R) and L(R′) in order for L(R) to be prefix-free.

4. Non-computability using a reduction from an undecidable language MAXIMUM_STEPS(k)

For this problem, we first define a computable function as follows: For a particular alphabet Σ, a function f: Σ*→ Σ*, i.e. a function that takes in the input string x and produces the output string y, so that f (x) = y, is computable if there exists a Turing machine that, when started with any string x as the input string on its tape, will halt with the output string y = f (x) on its tape.

Secondly, we describe a function called MAXIMUM_STEPS that takes a whole number as input and produces a whole number as output. This problem will ask you to show that MAXIMUM_STEPS is not computable.

Recall that, for a deterministic Turing Machine with a particular tape alphabet, the transition function tells us what the next step of execution is at any point. Given a current state and current tape symbol, a step is defined as: writing a symbol onto the tape, changing to a particular state, and moving either right or left.

We consider only Turing machines with a fixed number of k states. For any value of k, there are a finite number of Turing machines with k states. This is because a Turing machine is entirely determined by its transition function, and there are only finitely many such possible transition functions for a fixed number of k states.

Still considering the set of k-state Turing Machines, therefore, there are only a limited number of things that these machines can do on a particular input. For the purpose of this problem, we restrict our attention to the case where the input string is the empty string (for any Turing machine we can define the transitions to be made when faced with a blank symbol, so that an empty input string does not restrict the computations that the Turing machine can perform).

Because there are only finitely many Turing machines with k states, there are finitely many Turing machines with k states that halt (and finitely many that do not halt).
Therefore, there is a k-state Turing machine T, that halts on the empty string as input, such that no other Turing machine with k states takes longer (a larger number of steps) than T to halt. The function MAXIMUM_STEPS is equal to the number of steps that T takes to halt.

The function MAXIMUM_STEPS(k) is defined as follows:
For any whole number k > 0, MAXIMUM_STEPS(k) is the size of the longest sequence of steps that any Turing machine with k states can perform when started with the empty string on the input tape before halting. (This function gives one output value for a particular value of k, i.e. it considers all k-state machines together, and picks the running time of one that runs for the longest time before halting).

Show that the function MAXIMUM_STEPS(k) is not computable, i.e. that there is no TM that starts with a tape input of k (written in an appropriate format, e.g. as a string of k 1s) and writes as output the maximum number of steps that a k-state TM, starting with the input of an empty tape, can take before halting.

Hints for a solution: Suppose that, on the contrary, MAXIMUM_STEPS(k) is computable, i.e. that there exists a Turing machine MMS that computes it. Show that, in that case, you can use MMS to construct a decider for ATM, i.e. a Turing machine that can decide whether or not a particular Turing machine M will terminate on any input w or not.

Note that MMS does not itself necessarily contain k states; it is not itself the machine that takes the maximum number of steps for a given k. Instead MMS is a Turing machine that takes in any k as input and produces MAXIMUM_STEPS(k) as output.

Also note that, for a particular M and w, we can always construct a TM Mw, such that Mw ignores its own input, and just simulates the action of that particular M on that particular w, accepting/rejecting if M accepts/rejects, and looping if M loops.
Therefore, Mw will simulate M on w when started with the blank tape. You can make use of the machine Mw in your answer if you wish.

5. Undecidability using Rice's Theorem

Use Rice's Theorem to show that the language ALLTM is undecidable, where
ALL_TM = {<M> | M is a TM and L(M) = Σ*}.

(Show that both conditions for applying the theorem are true.)

Attachment:- Theory and Practice of Computing.rar