Third model of computation, Theory of Computation

Computer has a single LIFO stack containing ?xed precision unsigned integers (so each integer is subject to over?ow problems) but which has unbounded depth (so the stack itself never over?ows).

In your program you should limit yourself to accessing this with methods like push(i), top(), pop(), and a predicate like empty?(). These will push a value into the stack, return the value stored in the top of the stack (the most recent value pushed), discard the top of stack,
and test the stack for empty, respectively. Don't forget that you have no storage outside of the stack, so you need to work directly with the values in the stack-you can't pull a value out of the stack and assign it to some other variable. Similarly, while you can call input() as
often as you wish, the only way to store the value of the input is to push it directly into the stack (e.g., push(input())).

(a) Sketch an algorithm to recognize the language of strings of the form wcwr where w is any sequence of ‘a's and ‘b's and wr is exactly the same sequence of ‘a's and ‘b's in reverse order, so these are all palindromes over the alphabet {a, b, c} in which 'c' occurs only as the middle symbol. It includes strings like:

abbbcabbb aca ababacababa c

(In the last example there are no ‘a's or ‘b's, the "re?ected" string is empty.)

(b) What is your intuition about recognizing this language within the second model (i.e., using just a single counter)?

(c) What is your intuition about the possibility of recognizing the language of strings of the form wcw, where w is an arbitrary string of ‘a's and ‘b's? This is the set of strings made up of any sequence of ‘a's and ‘b's followed by a 'c' and then exactly the same sequence of ‘a's and ‘b's in exactly the same order; it's referred to as the (deterministic) copy language.

Posted Date: 3/20/2013 6:16:01 AM | Location : United States







Related Discussions:- Third model of computation, Assignment Help, Ask Question on Third model of computation, Get Answer, Expert's Help, Third model of computation Discussions

Write discussion on Third model of computation
Your posts are moderated
Related Questions
Let L1 and L2 be CGF. We show that L1 ∩ L2 is CFG too. Let M1 be a decider for L1 and M2 be a decider for L2 . Consider a 2-tape TM M: "On input x: 1. copy x on the sec

Describe the architecture of interface agency


When we study computability we are studying problems in an abstract sense. For example, addition is the problem of, having been given two numbers, returning a third number that is

State & prove pumping lemma for regular set. Show that for the language L={ap |p is a prime} is not regular

The fact that the Recognition Problem is decidable gives us another algorithm for deciding Emptiness. The pumping lemma tells us that if every string x ∈ L(A) which has length grea

#can you solve a problem of palindrome using turing machine with explanation and diagrams?

Our primary concern is to obtain a clear characterization of which languages are recognizable by strictly local automata and which aren't. The view of SL2 automata as generators le

The upper string r ∈ Q+ is the sequence of states visited by the automaton as it scans the lower string w ∈ Σ*. We will refer to this string over Q as the run of A on w. The automa

Question 2 (10 pt): In this question we look at an extension to DFAs. A composable-reset DFA (CR-DFA) is a five-tuple, (Q,S,d,q0,F) where: – Q is the set of states, – S is the alph