Alphabets - strings and representation, Theory of Computation

A finite, nonempty ordered set will be called an alphabet if its elements are symbols, or characters. A finite sequence of symbols from a given alphabet will be called a string over the alphabet. A string that consists of a sequence a1, a2, . . . , an of symbols will be denoted by the juxtaposition a1a2 Strings that have zero symbols, called empty strings, will be denoted by e.

{0, 1} is a binary alphabet, and {1} is a unary alphabet. 11 is a binary string over the alphabet {0, 1}, and a unary string over the alphabet {1}.

11 is a string of length 2, |ε| = 0, and |01| + |1| = 3.

Example-The string consisting of a sequence αβ followed by a sequence β is denoted αβ. The string αβ is called the concatenation of α and β. The notation αi is used for the string obtained by concatenating i copies of the string α.

Posted Date: 3/18/2013 1:02:49 AM | Location : United States

Related Discussions:- Alphabets - strings and representation, Assignment Help, Ask Question on Alphabets - strings and representation, Get Answer, Expert's Help, Alphabets - strings and representation Discussions

Write discussion on Alphabets - strings and representation
Your posts are moderated
Related Questions
Define the following concept with an example: a.    Ambiguity in CFG b.    Push-Down Automata c.    Turing Machine

A problem is said to be unsolvable if no algorithm can solve it. The problem is said to be undecidable if it is a decision problem and no algorithm can decide it. It should be note

(c) Can you say that B is decidable? (d) If you somehow know that A is decidable, what can you say about B?

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

The fact that regular languages are closed under Boolean operations simpli?es the process of establishing regularity of languages; in essence we can augment the regular operations

design a tuning machine for penidrome

How useful is production function in production planning?

Computations are deliberate for processing information. Computability theory was discovered in the 1930s, and extended in the 1950s and 1960s. Its basic ideas have become part of