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
De?nition Instantaneous Description of an FSA: An instantaneous description (ID) of a FSA A = (Q,Σ, T, q 0 , F) is a pair (q,w) ∈ Q×Σ* , where q the current state and w is the p

The Recognition Problem for a class of languages is the question of whether a given string is a member of a given language. An instance consists of a string and a (?nite) speci?cat


Lemma 1 A string w ∈ Σ* is accepted by an LTk automaton iff w is the concatenation of the symbols labeling the edges of a path through the LTk transition graph of A from h?, ∅i to

Distinguish between Mealy and Moore Machine? Construct a Mealy machine that can output EVEN or ODD According to the total no. of 1's encountered is even or odd.

Different types of applications and numerous programming languages have been developed to make easy the task of writing programs. The assortment of programming languages shows, dif

how to find whether the language is cfl or not?

The fundamental idea of strictly local languages is that they are speci?ed solely in terms of the blocks of consecutive symbols that occur in a word. We'll start by considering lan

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

One of the first issues to resolve, when exploring any mechanism for defining languages is the question of how to go about constructing instances of the mechanism which define part