How to solve the checking problem, Theory of Computation

Assignment Help:

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.


Related Discussions:- How to solve the checking problem

Equivalence of nfas and dfas, In general non-determinism, by introducing a ...

In general non-determinism, by introducing a degree of parallelism, may increase the accepting power of a model of computation. But if we subject NFAs to the same sort of analysis

Abstract model for an algorithm solving a problem, These assumptions hold f...

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

Turing machine, Design a turing machine to compute x + y (x,y > 0) with x a...

Design a turing machine to compute x + y (x,y > 0) with x an y in unary, seperated by a # (descrition and genereal idea is needed ... no need for all TM moves)

Myhill-nerode theorem, The Myhill-Nerode Theorem provided us with an algori...

The Myhill-Nerode Theorem provided us with an algorithm for minimizing DFAs. Moreover, the DFA the algorithm produces is unique up to isomorphism: every minimal DFA that recognizes

Myhill-nerode, Theorem (Myhill-Nerode) A language L ⊆ Σ is recognizable iff...

Theorem (Myhill-Nerode) A language L ⊆ Σ is recognizable iff ≡L partitions Σ* into ?nitely many Nerode equivalence classes. Proof: For the "only if" direction (that every recogn

Local myhill graphs, Myhill graphs also generalize to the SLk case. The k-f...

Myhill graphs also generalize to the SLk case. The k-factors, however, cannot simply denote edges. Rather the string σ 1 σ 2 ....... σ k-1 σ k asserts, in essence, that if we hav

Kleene Closure, 1. Does above all''s properties can be used to prove a lang...

1. Does above all''s properties can be used to prove a language regular? 2..which of the properties can be used to prove a language regular and which of these not? 3..Identify one

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?

D c o, Prove xy+yz+ýz=xy+z

Prove xy+yz+ýz=xy+z

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