Define the following: (i) Formal language Grammars. (ii) Terminal symbols. (iii) Alphabet and String.


Define the following:
(i) Formal language Grammars.

(ii) Terminal symbols.
(iii) Alphabet and String. 
 

Ans:

(i) Formal language Grammars

 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 start symbol.  

(ii) Terminal Symbols

 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 ax, then a is a terminal symbol because it cannot become something else. These are the symbols which can appear as it is in the programme. 

(iii)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.

12


Sometimes space and comma are in an alphabet while other times they are meta symbols used for descriptions. A language is defined over an 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.

0 comments:

Feel free to contact the admin for any suggestions and help.