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 ...an. 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


The k-local Myhill graphs provide an easy means to generalize the suffix substitution closure property for the strictly k-local languages. Lemma (k-Local Suffix Substitution Clo

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

The upper string r ∈ Q+ is the sequence of states visited by the automaton as it scans the lower string w ∈ Σ*. We will refer to this string over Q as the run of A on w. The automa

Claim Under the assumptions above, if there is an algorithm for checking a problem then there is an algorithm for solving the problem. Before going on, you should think a bit about

Generate 100 random numbers with the exponential distribution lambda=5.0.What is the probability that the largest of them is less than 1.0?

Rubber shortnote

Exercise:  Give a construction that converts a strictly 2-local automaton for a language L into one that recognizes the language L r . Justify the correctness of your construction.

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.