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

Finite state automata, Since the signi?cance of the states represented by t...

Since the signi?cance of the states represented by the nodes of these transition graphs is arbitrary, we will allow ourselves to use any ?nite set (such as {A,B,C,D,E, F,G,H} or ev

Two-tape turing machine, Let there L1 and L2 . We show that L1 ∩ L2 is CFG ...

Let there L1 and L2 . We show that L1 ∩ L2 is CFG . Let M1 be a decider for L1 and M2 be a decider for L2 . Consider a 2-tape TM M: "On input x: 1. copy x on the second

Closure properties of recognizable languages, We got the class LT by taking...

We got the class LT by taking the class SL and closing it under Boolean operations. We have observed that LT ⊆ Recog, so certainly any Boolean combination of LT languages will also

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

Sketch an algorithm to recognize the language, First model: Computer has a ...

First model: Computer has a ?xed number of bits of storage. You will model this by limiting your program to a single ?xed-precision unsigned integer variable, e.g., a single one-by

Java programming, 1. An integer is said to be a “continuous factored” if it...

1. An integer is said to be a “continuous factored” if it can be expresses as a product of two or more continuous integers greater than 1. Example of continuous factored integers

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?

Turing machine, Design a turing machine to compute x + y (x,y > 0) with x a...

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)

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