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

push(input()).

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
In Exercise 9 you showed that the recognition problem and universal recognition problem for SL2 are decidable. We can use the structure of Myhill graphs to show that other problems

The path function δ : Q × Σ*→ P(Q) is the extension of δ to strings: Again, this just says that to ?nd the set of states reachable by a path labeled w from a state q in an

Exercise Show, using Suffix Substitution Closure, that L 3 . L 3 ∈ SL 2 . Explain how it can be the case that L 3 . L 3 ∈ SL 2 , while L 3 . L 3 ⊆ L + 3 and L + 3 ∈ SL

We'll close our consideration of regular languages by looking at whether (certain) problems about regular languages are algorithmically decidable.

Paths leading to regions B, C and E are paths which have not yet seen aa. Those leading to region B and E end in a, with those leading to E having seen ba and those leading to B no

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

. On July 1, 2010, Harris Co. issued 6,000 bonds at $1,000 each. The bonds paid interest semiannually at 5%. The bonds had a term of 20 years. At the time of issuance, the market r


These assumptions hold for addition, for instance. Every instance of addition has a unique solution. Each instance is a pair of numbers and the possible solutions include any third

Our DFAs are required to have exactly one edge incident from each state for each input symbol so there is a unique next state for every current state and input symbol. Thus, the ne