 Formal Language Grammars, (2) Terminal Symbols, (3) Alphabet and String.){kind=link}
Answer:
1.
A
Formal Language Grammar is
a set of formation rules that describe which strings formed from the alphabet
of a formal language are syntactically valid, within the language. A grammar
only addresses the location and manipulation of the strings of the language. It
does not describe anything else about a language, such as its semantics.
As proposed by Noam Chomsky, a grammar G consists of
the following components:
·
A
finite set N of non-terminal symbols.
·
A
finite set Σ of terminal symbols That is disjoint from N.
·
A
finite set P of production rules, each rule of the form.
Where * is the Kleene star operator and denotes set union.
That is, each production rule maps from one string of symbols to another, where
the first string contains at least one non terminal symbol.
·
A
distinguished non terminal symbol from set N that is the star symbol.
2.
Terminal
Symbols are literal
strings forming the input of a formal grammar and cannot be broken down into
smaller units without losing their literal meaning. In simple words, terminal
symbols cannot be changed using the rules of the grammar; that is, they’re the
end of the line, or terminal. For example, if the grammar rules are that x
can become xa and x can become xa,
then a is a terminal symbol because it cannot become something else. These are
the symbols which can appear as it is the programme.
3.
Alphabet
and String: A finite set
of symbols is called alphabet. An alphabet is often denoted by sigma, yet can
be given any name.
B = {0,1} says B is an alphabet of two symbols, 0 and
1.
C = {a, b, c,} says C is an alphabet of three symbols,
a, b, and c.
Sometimes space and comma are in an alphabet while other
times they are meta symbols used for descriptions. A language is defined over
and alphabet. For Example, binary language is defined over alphabet B.
A finite sequence of symbols from an alphabet is
called string or word.
01110 and 111 are strings from the alphabet B above.
aaabccc and b are strings from the alphabet C above.
A null string is a string with no symbols, usually
denoted by epsilon has zero length.
Post a Comment