Sketch an algorithm to recognize the language, Theory of Computation

Assignment Help:

First model: Computer has a ?xed number of bits of storage. You will model this by limiting your program to a single ?xed-precision unsigned integer variable, e.g., a single one-byte variable (which, of course, can store only values in the range [0, . . . , 255]), etc. Limityourself, further, to calling input() in just one place in your program. One way of doing this is to call input() in the argument of a multiway branch (e.g., switch) statement. (That statement, of course, will need to be in the scope of some sort of loop, otherwise you would never read more than the ?rst symbol of the input.) The reason for this restriction will become clear in the last part of this question.

(a) Sketch an algorithm to recognize the language: {(ab)i | i ≥ 0} (that is, the set of strings of ‘a's and ‘b's consisting of zero or more repetitions of ab: {ε, ab, abab, ababab, . . .}, where ‘ε' is the empty string, containing no symbols whatsoever).

(b) How many bits do you need for this (how much precision do you need)? Can you do it with a single bit integer?

(c) Sketch an algorithm to recognize the language: {(abbba)i | i ≥ 0} (i.e., {ε, abbba, abbbaabbba, . . .}).

(d) How many bits do you need for this?

(e) Suppose we relax the limitation to calling input() at a single place in the code. Sketch an algorithm for recognizing the language of part (a) using (apparently) no data storage.

[Hint: All you need to do is to verify that the ‘a's and ‘b's occur in the right sequence. If you forget all the restrictions, etc., and just use the simplest program you can think of, you are likely to come up with one that meets these criteria.]

Argue that any algorithm for recognizing this language must store at least one bit of information. Where does your program store it?


Related Discussions:- Sketch an algorithm to recognize the language

Local and recognizable languages, We developed the idea of FSA by generaliz...

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

Bonds, . On July 1, 2010, Harris Co. issued 6,000 bonds at $1,000 each. The...

. 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

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

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

Computations of sl automata, We will specify a computation of one of these ...

We will specify a computation of one of these automata by specifying the pair of the symbols that are in the window and the remainder of the string to the right of the window at ea

Qbasic, Ask question #Minimum 100 words accepte

Ask question #Minimum 100 words accepte

Finite languages and strictly local languages, Theorem The class of ?nite l...

Theorem The class of ?nite languages is a proper subclass of SL. Note that the class of ?nite languages is closed under union and concatenation but SL is not closed under either. N

Answer, And what this money. Invovle who it involves and the fact of,how we...

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

Discrete math, Find the Regular Grammar for the following Regular Expressio...

Find the Regular Grammar for the following Regular Expression: a(a+b)*(ab*+ba*)b.

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