DERIVATIONS AND THE LANGUAGE GENERATED BY A GRAMMAR Productions are used to derive one stling over \/N U L from another string. We give a formal definition of derivation as follows: Definition 4.2 If a f3 is a production in a grammar G and y, 8 are any two strings on U 2:, then we say that ya8 directly derives yf38 in G (we "\!fite this as ya8 yf38). This process is called one-step derivation. In G particular. if a ---1 f3 is a production. then a f3. G Note: If a is a part of a stling and a f3 is a production. we can replace a by f3 in that string (without altenng the remaining parts). In this case we say that the string we started with directly derives the new string. For example, G = US}. {O. I}, {S -t 051. S -t Ol}, 5) has the production 5 ---1 OS1. So, 5 in 04S14 can be replaced by 051. The resulting string is 04 0511". Thus. we have 04 51"+ 0"OS114. G Note: induces a relation R on IVy U 2:)*. i.e. aRf3 if a [3. G G Defmition 4.3 If a and f3 are strings on \/v U :E, then we say that a derives ~, '" f3 if a f3. Here denotes the reflexive-transitive closure of the relation G G G in (Fy U :E)* (refer to Section 2.1.5). Note: We can note in particular that a 7 a. Also, if a 7 f3. [X '1'= f3, then there exist strings [Xl- a2, .. " (tll' where II ;::: 2 such that (X = (X] a2 a3 . .. all = f3 G G G When a f3 is in n steps. we write a b f3. G G Consider. for example. G = ({5}, {O. I}. {S -t OSl, 5 -t OIl, 5). * As S 051 02S12 ::::? 03S1 3 , we have S 03S1 3. We also have G G G G 03 513 03 513 (as (X a). G G Definition 4.4 The language generated by a grammar G (denoted by L(G)) is defined as {w E :E* IS 7 H}. The elements of L(G) are called sentences. Stated in another way, L(G) is the set of all terminal strings derived from the start symbol S. Definition 4.5 If 5 ,;, ex, then a is called a sentential form. We can note G that the elements of L(G) are sentential forms but not vice versa

Definition 4.6 Gi and G: are equivalent if L(GJ =L(G:). Remarks on Derivation 1. Any derivation involves the application of productions. When the number of times we apply productions is one, we write a =? {3; when .,. e it is more than one, \ve \vrite CY. f3 (Note: a a). e G ") The string generated by the most recent application of production is called the working string. 3. The derivation of a string is complete when the working string cannot be modified. If the final string does not contain any variable. it is a sentence in the language. If the final string contains a variable. it is a sentential form and in this case the production generator gets 'stuck'. NOTATION: (i) We \vrite CY. {3 simply as CY. :b {3 if G is clear from the context. e (ji) If A CY. is a production where A E Vv, then it is called an A-production. (iii) If A ai' A. a:. .. nA. CY.!/! are A-productions. these productions are written as A ai i CY.: j ... I am' We give several examples of grammars and languages generated by them.

QUESTION E 4.2 If G = ({5}. {a. I}. {5 051, s A}. S). find L(G).

QUESTION If G = ({ 5}, {a}, {5 ----;; 55}, 5), find the language generated by G.

QUESTION Let G =({ S. C}, {a, b}, P, 5), where P consists of 5 ----;; aCa. C ----;; aCa I b. Find L(G).

Transcribed Image Text:

Example 1-2 10 2 WIN NIN -IN = = II Integer quotient 20 10 11 5 = 2 1 + = 0 + 0 1/11 answer: (41) 10 = (asaa3aaa0) = (101001)2 41 20 10 Remainder 1/1/2 0 5 2 1 0 0 -IN 0 153 Coefficient a = 1 The arithmetic process can be manipulated more conveniently as follows: Integer Remainder 19 1 23 012 L a = 0 a = 0) = (231), a3 1 a = 0 101001 = answer The conversion from decimal integers to any base-r system is similar to the exam- ple, except that division is done by r instead of 2. as = 1 Convert decimal 153 to octal. The required baser is 8. First, 153 is divided by 8 to give an integer quotient of 19 and a remainder of 1. Then 19 is divided by 8 to give an integer quotient of 2 and a remainder of 3. Finally, 2 is divided by 8 to give a quotient of 0 and a remainder of 2. This process can be conveniently manipulated as follows: Example 1-2 10 2 WIN NIN -IN = = II Integer quotient 20 10 11 5 = 2 1 + = 0 + 0 1/11 answer: (41) 10 = (asaa3aaa0) = (101001)2 41 20 10 Remainder 1/1/2 0 5 2 1 0 0 -IN 0 153 Coefficient a = 1 The arithmetic process can be manipulated more conveniently as follows: Integer Remainder 19 1 23 012 L a = 0 a = 0) = (231), a3 1 a = 0 101001 = answer The conversion from decimal integers to any base-r system is similar to the exam- ple, except that division is done by r instead of 2. as = 1 Convert decimal 153 to octal. The required baser is 8. First, 153 is divided by 8 to give an integer quotient of 19 and a remainder of 1. Then 19 is divided by 8 to give an integer quotient of 2 and a remainder of 3. Finally, 2 is divided by 8 to give a quotient of 0 and a remainder of 2. This process can be conveniently manipulated as follows: