First model of computation, Theory of Computation

Computer has a single unbounded precision counter which you can only increment, decrement and test for zero. (You may assume that it is initially zero or you may include an explicit instruction to clear.) Limit your program to a single unsigned integer variable, and limit your methods of accessing it to something like inc(i), dec(i) and a predicate zero?(i) which returns true i? i = 0. This integer has unbounded precision-it can range over the entire set of natural numbers-so you never have to worry about your counter over?owing. It is, however, restricted to only the natural numbers-it cannot go negative, so you cannot decrement past zero.

(a) Sketch an algorithm to recognize the language: {aibi| i ≥ 0}. This is the set of strings consisting of zero or more ‘a's followed by exactly the same number of ‘b's.

(b) Can you do this within the ?rst model of computation? Either sketch an algorithm to do it, or make an informal argument thatit can't be  done.

(c) Give an informal argument that one can't recognize the language: {aibici| i ≥ 0} within this second model of computation (i.e, with
a single counter)

Posted Date: 3/20/2013 6:13:41 AM | Location : United States

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

Write discussion on First model of computation
Your posts are moderated
Related Questions
The project 2 involves completing and modifying the C++ program that evaluates statements of an expression language contained in the Expression Interpreter that interprets fully pa

Normal forms are important because they give us a 'standard' way of rewriting and allow us to compare two apparently different grammars G1  and G2. The two grammars can be shown to

Suppose A = (Q,Σ, T, q 0 , F) is a DFA and that Q = {q 0 , q 1 , . . . , q n-1 } includes n states. Thinking of the automaton in terms of its transition graph, a string x is recogn

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

spam messages h= 98%, m= 90%, l= 80% non spam h=12%, m = 8%, l= 5% The organization estimates that 75% of all messages it receives are spam messages. If the cost of not blocking a

Applying the pumping lemma is not fundamentally di?erent than applying (general) su?x substitution closure or the non-counting property. The pumping lemma is a little more complica

This was one of the ?rst substantial theorems of Formal Language Theory. It's maybe not too surprising to us, as we have already seen a similar equivalence between LTO and SF. But

Define the following concept with an example: a.    Ambiguity in CFG b.    Push-Down Automata c.    Turing Machine

This close relationship between the SL2 languages and the recognizable languages lets us use some of what we know about SL 2 to discover properties of the recognizable languages.

i want to do projects for theory of computation subject what topics should be best.