GMDB for cs402 will be opened on Monday 31st of January, 2011; the topic for GMD

[admin]

GMDB for cs402 will be opened on Monday 31st of January, 2011; the topic for GMDB is,

"Formal Languages set is superset of Regular Languages set"



Note: You can post your comments one time only on GMDB within two days of launch of GMDB.

[admin]

In theoretical computer science, a regular language is a formal language (i.e., a possibly infinite set of finite sequences of symbols from a finite alphabet) that satisfies the following equivalent properties:
?   it can be accepted by a deterministic finite state machine.
?   it can be accepted by a nondeterministic finite state machine
?   it can be accepted by an alternating finite automaton
?   it can be described by a formal regular expression. Note that the "regular expression" features provided with many programming languages are augmented with features that make them capable of recognizing languages which are not regular, and are therefore not strictly equivalent to formal regular expressions.
?   it can be generated by a regular grammar
?   it can be generated by a prefix grammar
?   it can be accepted by a read-only Turing machine
?   it can be defined in monadic second-order logic
?   it is recognized by some finitely generated monoid
?   it is the preimage of a subset of a finite monoid under a homomorphism from the free monoid on its alphabet
The collection of regular languages over an alphabet ? is defined recursively as follows:
?   the empty language Ø is a regular language.
?   the empty string language { ? } is a regular language.
?   For each a ? ? (a belongs to ? ), the singleton language { a } is a regular language.
?   If A and B are regular languages, then A ? B (union), A • B (concatenation), and A* (Kleene star) are regular languages.
?   No other languages over ? are regular.
All finite languages are regular. Other typical examples include the language consisting of all strings over the alphabet {a, b} which contain an even number of as, or the language consisting of all strings of the form: several as followed by several bs.
A simple example of a language that is not regular is the set of strings  .
Regular language
One regular language is one formal language, which is subject to a set of relatively strict restrictions.
A formal language e.g. differs from a natural speech. because arbitrary symbol sequences as Word are designated. The quantity of the symbols permitted for a word is called Alphabet. One calls a quantity of words, which consist of such permitted symbols, a formal language.

Table of contents
•   1 Characteristics
•   2 Definition
•   3 Proof of the regularity of a language
•   4 Examples
•   5 Conclusion characteristics
•   6 Typical decision problems
•   7 Literature

Characteristics
Whether a language is more or less reduced, results from its position within that Chomsky hierarchy. One means the quantityeverything , then one speaks regular languages also of that Class the regular languages. The class of the regular languages belongs within the Chomsky hierarchy to most reduced language classes of the so-called Type 3 on. They form thereby a genuine subset for that context-free languages, which are less reduced. It concerns a very natural language class nevertheless, in thatLinguistics, that Computer science, as well as with the construction of mechanical devices a high practical meaning attained.
Definition
A language L over an alphabet ?, i.e. a quantity of words, is regularly called if it fulfills one of the following equivalent conditions:
•   L becomes from one regular grammar produced.
•   L becomes from one finite automats accepted.
•   L can by one regular expression are represented.
•   Up ? * by defined Relation RL finite has Index (Sentence of Myhill Nerode).
•   L can in the Monadi logic 2. Stage to be defined
Proof of the regularity of a language
If one wants to prove for a given language that she is regular, then one must her therefore on a regular grammar, a finite automat or a regular expression or to already well-known regular languages to attribute. For a proof that a language L , is mostly appropriate it is not regular, that Pumping Lemma (= Pumplemma) to use for regular languages or prove in more difficult cases that the index of RL is not finite.
Examples
Is ? an alphabet.
•   All finally acceptable languages, are regular.
•   Everything context-free languages over a unären alphabet, i.e. , are regular.
Conclusion characteristics
The class of the regular languages is locked under the usual Set operations Combination, Average and Complement. Beyond that the compartmentation applies also to those Konkatenation and the so-called Clover nests. In detail applies thus:
•   Those Combination two regular languages L1 and L2 is regular.
•   That Average two regular languages L1 and L2 is regular.
•   That Complement a regular language L is regular.
•   Those Konkatenation two regular languages L1 and L2 is regular.
•   That Clover nests L * a regular language L, i.e. the arbitrarily frequent Konkatenation of words from the language L combined with the empty word, is regular.
Typical decision problems
Are L, L1 and L2 given regular languages over the alphabet ?. Then the following typical problem definitions result:
•   Word problem: Listens a word L?
•   Empty heating problem: Is L the empty quantity?
•   Endlichkeitsproblem: Exists L from a finite quantity of words?
•   Equivalence problem: Applies L1 = L2?
All these problems are decidably. They also still apply - with an exception - to the similarly formulated problems over the context-free languages. The exception is the equivalence problem, which is no longer decidable already starting from the context-free languages (thus the language class next higher after the Chomsky hierarchy).
Literature
•   Michael Sipser: Introduction ton the Theory OF Computation, PWS Publishing (1997) - Chapter 1, regularly LANGUAGEs
•   Uwe Schöning: Theoretical computer science - abridged, Spectrum (2001) - chapter 1.2, regular one languages
•   John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Introduction to the automata theory, formal one languages and complexity theory, Pearson study (2002)


::..Discuss your vu Solution here, post or upload solution here. If you want Assignment solutions, help in gdb, or want solved quizes or past papers, you can ask here...be a part of this great website i.e. vu.ysapak.com ...::

[admin]

In theoretical computer science, a regular language is a formal language that satisfies the following equivalent properties:
it can be accepted by a deterministic finite state machine.
it can be accepted by a nondeterministic finite state machine
it can be accepted by an alternating finite automaton
it can be described by a formal regular expression. Note that the "regular expression" features provided with many programming languages are augmented with features that make them capable of recognizing languages which are not regular, and are therefore not strictly equivalent to formal regular expressions.
it can be generated by a regular grammar
it can be generated by a prefix grammar
it can be accepted by a read-only Turing machine
it can be defined in monadic second-order logic
it is recognized by some finitely generated monoid
it is the preimage of a subset of a finite monoid under a homomorphism from the free monoid on its alphabet
::..Discuss your vu Solution here, post or upload solution here. If you want Assignment solutions, help in gdb, or want solved quizes or past papers, you can ask here...be a part of this great website i.e. vu.ysapak.com ...::