How to solve the checking problem, Theory of Computation

The objective of the remainder of this assignment is to get you thinking about the problem of recognizing strings given various restrictions to your model of computation. We will work with whatever representation of an algorithm you are comfortable with (C or Pascal or, perhaps, some form of pseudo-code-just make sure it is unambiguous). Don't get too carried away with this. You only have a short time to work on it. The goal is primarily to think about this stu?, not to agonize over it. Whatever you do, don't turn it into a programming assignment; running code is not a bonus in this case.

In all of the problems we will assume the same basic machine:

• The program is read-only (it can't be modi?ed, you might even think of it as being hard-wired).

• For the sake of uniformity, let's assume the following methods for accessing the input:

- input(), a function that returns the current input character. You can use this in forms like

i ← input(), or

if (input() = ‘a' ) then . . . , or


This does not consume the character; any subsequent calls to input() prior to a call to next() will return the same character. You may assume that input() returns a unique value EOF if all of the input has been consumed.

- next(), a function that bumps to the next position in the input.

This discards the previous character which cannot be re-read. You can either assume that it returns nothing or that it returns TRUE in the case the input is not at EOF and FALSE otherwise.

Posted Date: 3/20/2013 6:08:24 AM | Location : United States

Related Discussions:- How to solve the checking problem, Assignment Help, Ask Question on How to solve the checking problem, Get Answer, Expert's Help, How to solve the checking problem Discussions

Write discussion on How to solve the checking problem
Your posts are moderated
Related Questions
If the first three words are the boys down,what are the last three words??

Intuitively, closure of SL 2 under intersection is reasonably easy to see, particularly if one considers the Myhill graphs of the automata. Any path through both graphs will be a

We developed the idea of FSA by generalizing LTk transition graphs. Not surprisingly, then, every LTk transition graph is also the transition graph of a FSA (in fact a DFA)-the one

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

Automaton (NFA) (with ε-transitions) is a 5-tuple: (Q,Σ, δ, q 0 , F i where Q, Σ, q 0 and F are as in a DFA and T ⊆ Q × Q × (Σ ∪ {ε}). We must also modify the de?nitions of th

And what this money. Invovle who it involves and the fact of,how we got itself identified candidate and not withstanding time date location. That shouts me media And answers who''v

When an FSA is deterministic the set of triples encoding its edges represents a relation that is functional in its ?rst and third components: for every q and σ there is exactly one

Another way of representing a strictly 2-local automaton is with a Myhill graph. These are directed graphs in which the vertices are labeled with symbols from the input alphabet of

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