Formal languages and grammar, Theory of Computation

The universe of strings is a very useful medium for the representation of information as long as there exists a function that provides the interpretation for the information carried by the strings. An interpretation is just the contrary of the mapping that a representation provides, that is, an interpretation is a function g from Σ* to D for some alphabet Σ and some set D. The string 111, for instance, can be interpreted as the number one hundred and eleven represented by a decimal string, as the number seven represented by a binary string, and as the number three represented by a unary string.

In general, if Σ is an alphabet and L is a subset of Σ*, then L is said to be a language over Σ, or simply a language if Σ is understood. Each element of L is said to be a sentence or a word or a stringof the language.

"Example- {0, 11, 001}, {ε, 10}, and {0, 1}* are subsets of {0, 1}*, and so they are languages over the alphabet {0, 1}.

The empty set Ø and the set {ε} are languages over every alphabet. Ø is a language that contains no string. {ε} is a language that contains just the empty string.

The union of two languages L1 and L2, denoted L1 U  L2, refers to the language that consists of all the strings that are either in L1 or in L2, that is, to { x | x is in L1 or x is in L2 }. The intersection of L1 and L2, denoted L1 ∩  L2, refers to the language that consists of all the strings that are both in L1 and L2, that is, to {x | x is in L1 and in L2}. The complementation of a language L over Σ, or just the complementation of L when Σ is understood, denoted L, refers to the language that consists of all the strings over Σ that are not in L, that is, to { x | x is in Σ* but not in L }".

A set of real values for a problem is called an instance of the problem. So a problem, specifies what an instance is, i.e., what is the input, problem, or output and how the solution is related to the input.

Posted Date: 3/18/2013 1:09:01 AM | Location : United States







Related Discussions:- Formal languages and grammar, Assignment Help, Ask Question on Formal languages and grammar, Get Answer, Expert's Help, Formal languages and grammar Discussions

Write discussion on Formal languages and grammar
Your posts are moderated
Related Questions
What is the purpose of GDTR?

Find the Regular Grammar for the following Regular Expression:                    a(a+b)*(ab*+ba*)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

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

We will specify a computation of one of these automata by specifying the pair of the symbols that are in the window and the remainder of the string to the right of the window at ea

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

Design a turing machine to compute x + y (x,y > 0) with x an y in unary, seperated by a # (descrition and genereal idea is needed ... no need for all TM moves)

The class of Strictly Local Languages (in general) is closed under • intersection but is not closed under • union • complement • concatenation • Kleene- and positive

The initial ID of the automaton given in Figure 3, running on input ‘aabbba' is (A, aabbba) The ID after the ?rst three transitions of the computation is (F, bba) The p

conversion from nfa to dfa 0 | 1 ___________________ p |{q,s}|{q} *q|{r} |{q,r} r |(s) |{p} *s|null |{p}