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
how to write program Minimum Cost Calculation - Vogel Approximation Method(VAM


Another striking aspect of LTk transition graphs is that they are generally extremely ine?cient. All we really care about is whether a path through the graph leads to an accepting

Sketch an algorithm for the universal recognition problem for SL 2 . This takes an automaton and a string and returns TRUE if the string is accepted by the automaton, FALSE otherwi

Find the Regular Grammar for the following Regular Expression: a(a+b)*(ab*+ba*)b.

What is the purpose of GDTR?

Construct a PDA that accepts { x#y | x, y in {a, b}* such that x ? y and xi = yi for some i, 1 = i = min(|x|, |y|) }. For your PDA to work correctly it will need to be non-determin

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

Automata and Compiler (1) [25 marks] Let N be the last two digits of your student number. Design a finite automaton that accepts the language of strings that end with the last f

write grammer to produce all mathematical expressions in c.