First model of computation, Theory of Computation

Assignment Help:

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)


Related Discussions:- First model of computation

Computation and languages, When we study computability we are studying prob...

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

Ogdens lemma, proof ogdens lemma .with example i am not able to undestand ...

proof ogdens lemma .with example i am not able to undestand the meaning of distinguished position .

Two-tape turing machine, Let there L1 and L2 . We show that L1 ∩ L2 is CFG ...

Let there L1 and L2 . We show that L1 ∩ L2 is CFG . 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 second

Prepare the consolidated financial statements, Prepare the consolidated fin...

Prepare the consolidated financial statements for the year ended 30 June 2011. On 1 July 2006, Mark Ltd acquired all the share capitall of john Ltd for $700,000. At the date , J

Mapping reducibility, Can you say that B is decidable? If you somehow know...

Can you say that B is decidable? If you somehow know that A is decidable, what can you say about B?

Automaton for finite languages, We can then specify any language in the cla...

We can then specify any language in the class of languages by specifying a particular automaton in the class of automata. We do that by specifying values for the parameters of the

Synthesis theorem, Kleene called this the Synthesis theorem because his (an...

Kleene called this the Synthesis theorem because his (and your) proof gives an effective procedure for synthesizing an automaton that recognizes the language denoted by any given r

Pumping lemma, For every regular language there is a constant n depending o...

For every regular language there is a constant n depending only on L such that, for all strings x ∈ L if |x| ≥ n then there are strings u, v and w such that 1. x = uvw, 2. |u

Normal forms, how to convert a grammar into GNF

how to convert a grammar into GNF

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd