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

Strictly 2-local languages, The fundamental idea of strictly local language...

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

Defining strictly local automata, One of the first issues to resolve, when ...

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

Grammer, write grammer to produce all mathematical expressions in c.

write grammer to produce all mathematical expressions in c.

Non deterministic finite state automaton, Automaton (NFA) (with ε-transitio...

Automaton (NFA) (with ε-transitions) is a 5-tuple: (Q,Σ, δ, q 0 , F i where Q, Σ, q 0 and F are as in a DFA and T ⊆ Q × Q × (Σ ∪ {ε}). We must also modify the de?nitions of th

Complement - operations on languages, The fact that SL 2 is closed under i...

The fact that SL 2 is closed under intersection but not under union implies that it is not closed under complement since, by DeMorgan's Theorem L 1 ∩ L 2 = We know that

Two-tape turing machine, Let there L1 and L2 . We show that L1 ∩ L2 is CFG ...

Let there L1 and L2 . We show that L1 ∩ L2 is CFG . Let M1 be a decider for L1 and M2 be a decider for L2 . Consider a 2-tape TM M: "On input x: 1. copy x on the second

Dfa to re, c program to convert dfa to re

c program to convert dfa to re

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