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.


Related Discussions:- Formal languages and grammar

Pendulum Swings, how many pendulum swings will it take to walk across the c...

how many pendulum swings will it take to walk across the classroom?

Regular expressions, The project 2 involves completing and modifying the C+...

The project 2 involves completing and modifying the C++ program that evaluates statements of an expression language contained in the Expression Interpreter that interprets fully pa

Finiteness problem for regular languages, The fact that the Recognition Pro...

The fact that the Recognition Problem is decidable gives us another algorithm for deciding Emptiness. The pumping lemma tells us that if every string x ∈ L(A) which has length grea

Venkatesh, What is the arbwnememmsmdbdbfbfjmfksmjejfnfnfnnrndmnfjfjfnrnkrkf...

What is the arbwnememmsmdbdbfbfjmfksmjejfnfnfnnrndmnfjfjfnrnkrkfjfnfmkrjrbfbbfjfnfjruhrvrjkgktithhrbenfkiffnbr ki rnrjjdjrnrk bd n FBC..jcb?????????????????????????????????????????

Positiveness problem - decision problems, For example, the question of whet...

For example, the question of whether a given regular language is positive (does not include the empty string) is algorithmically decidable. "Positiveness Problem". Note that

Pendulum Swings, how many pendulum swings will it take to walk across the c...

how many pendulum swings will it take to walk across the classroom?

Myhill graph of the automaton, Exercise:  Give a construction that converts...

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.

Prepare the consolidated financial statements, Prepare the consolidated fin...

Prepare the consolidated financial statements for the year ended 30 June 2011. On 1 July 2006, Mark Ltd acquired all the share capitall of john Ltd for $700,000. At the date , J

Possibility of recognizing the palindrome language, Computer has a single F...

Computer has a single FIFO queue of ?xed precision unsigned integers with the length of the queue unbounded. You can use access methods similar to those in the third model. In this

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd