Sketch an algorithm to recognize the language, Theory of Computation

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?

Posted Date: 3/20/2013 6:11:52 AM | Location : United States

Related Discussions:- Sketch an algorithm to recognize the language, Assignment Help, Ask Question on Sketch an algorithm to recognize the language, Get Answer, Expert's Help, Sketch an algorithm to recognize the language Discussions

Write discussion on Sketch an algorithm to recognize the language
Your posts are moderated
Related Questions
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

Normal forms are important because they give us a 'standard' way of rewriting and allow us to compare two apparently different grammars G1  and G2. The two grammars can be shown to

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

Given any NFA A, we will construct a regular expression denoting L(A) by means of an expression graph, a generalization of NFA transition graphs in which the edges are labeled with

Let ? ={0,1} design a Turing machine that accepts L={0^m 1^m 2^m } show using Id that a string from the language is accepted & if not rejected .

The Universality Problem is the dual of the emptiness problem: is L(A) = Σ∗? It can be solved by minor variations of any one of the algorithms for Emptiness or (with a little le

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

LTO was the closure of LT under concatenation and Boolean operations which turned out to be identical to SF, the closure of the ?nite languages under union, concatenation and compl

examples of decidable problems