## Formal languages and grammar, Theory of Computation

Assignment Help:

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.

#### Ogdens lemma, proof ogdens lemma .with example i am not able to undestand ...

proof ogdens lemma .with example i am not able to undestand the meaning of distinguished position .

#### Notes, write short notes on decidable and solvable problem

write short notes on decidable and solvable problem

#### Decidability, examples of decidable problems

examples of decidable problems

#### First model of computation, Computer has a single unbounded precision count...

Computer has a single unbounded precision counter which you can only increment, decrement and test for zero. (You may assume that it is initially zero or you may include an explici

#### Chomsky normal form, s-> AACD A-> aAb/e C->aC/a D-> aDa/bDb/e

s-> AACD A-> aAb/e C->aC/a D-> aDa/bDb/e

#### Gdtr, What is the purpose of GDTR?

What is the purpose of GDTR?

#### Kleene closure, One might assume that non-closure under concatenation would...

One might assume that non-closure under concatenation would imply non closure under both Kleene- and positive closure, since the concatenation of a language with itself is included

#### Decision Theroy, spam messages h= 98%, m= 90%, l= 80% non spam h=12%, m = 8...

spam messages h= 98%, m= 90%, l= 80% non spam h=12%, m = 8%, l= 5% The organization estimates that 75% of all messages it receives are spam messages. If the cost of not blocking a

#### Regular languages, LTO was the closure of LT under concatenation and Boolea...

LTO was the closure of LT under concatenation and Boolean operations which turned out to be identical to SF, the closure of the ?nite languages under union, concatenation and compl

#### Perfect induction, A.(A+C)=A

A.(A+C)=A  