Language to Grammar Conversion:
For understanding language to grammar conversion, let us take an example-
Example 1- Consider the following language-
L(G) = { an bn | n>=1}
Solution: The above language is the combination of strings of 'a' and 'b' having equal number of 'a' and 'b'.
For making grammar corresponding to above language, first of all we start with starting symbol 'S'.
First production is S -> aSb (since number of a's come before number of b's and number of a's equal to number of b's. so we wrote aSb. with this rule, we can increase number of a's and number of b's.
Like S -> aSb -> aaSbb -> aaaSbbb...........
here we put the value of 'S' again and again and make strings.but with this rule , we can not eliminate Variable 'S'. so we have to write another rule that can eliminate 'S' from strings.
S -> ab
this rule makes first string and also eliminate 'S' from the strings produced by first rule.
Final Grammar corresponding to the above language is :
{ S -> aSb | ab }
string generated by the above grammar are:
{ab, aabb, aaabbb, aaaabbbb,.............} that is also accepted by the above language.
Example 2: Consider the following language-
L(G) = { an b2n | n>=1}
Example 3: Consider the following language-
L(G) = { a2n bn | n>=1}
Example 4: Consider the following language-
L(G) = { an bm an| n, m >= 1}
Example 5: Find out the grammar correspond to following language-
L(G) = { ai bm cm| m >= 1, i>=0}
solution: Grammar corresponding to above language are-
S -> aS | A
A -> bAc | bc
since there is no relation between i and m. so first of all, we have inserted number of a's using S -> aS production rule.
also the above language will generate strings that contains number of b's and c's only. so we have used S -> A production rule. and for number of b's and c's in equal manner, we have used A -> bAc | bc production rules.
Example 7: Find out the grammar correspond to following language-
L(G) = { w c wT| w contains strings of 0's and 1's including null}
Solution: Grammar corresponding to above language are
S -> aSa | bSb | c
since the above language also contains null so we have used S -> c production.
also w contains all the string of 0's and 1's and wT contains all the string of 1's and 0's ( wT means transpose of w). so we have used productions -
S -> aSa | bSb.
Example 8: Let L be the set of all palindrome strings over (0, 1). Construct G generating L.
Solution : Grammar (G) corresponding to above language are-
S -> ^
S -> 0 S -> 1
S -> 0S1 S -> 1S1
since ^ , 0 and 1 are single terminals. and single terminals always a palindrome string. so we have used S -> ^ S -> 0 S -> 1 production rules.
also for other strings of 0's and 1's, we have used production rules S -> 0S0 and S -> 1S1.
Example 9: Construct a grammar generating {am bm cm | n>=1 }
Solution: Grammar (G) corresponding to above language are-
S -> aSAc | abc
cA -> Ac
bA -> bb
other good examples, I will cover later.
Solution: The above language is the combination of strings of 'a' and 'b' having equal number of 'a' and 'b'.
For making grammar corresponding to above language, first of all we start with starting symbol 'S'.
First production is S -> aSb (since number of a's come before number of b's and number of a's equal to number of b's. so we wrote aSb. with this rule, we can increase number of a's and number of b's.
Like S -> aSb -> aaSbb -> aaaSbbb...........
here we put the value of 'S' again and again and make strings.but with this rule , we can not eliminate Variable 'S'. so we have to write another rule that can eliminate 'S' from strings.
S -> ab
this rule makes first string and also eliminate 'S' from the strings produced by first rule.
Final Grammar corresponding to the above language is :
{ S -> aSb | ab }
string generated by the above grammar are:
{ab, aabb, aaabbb, aaaabbbb,.............} that is also accepted by the above language.
Example 2: Consider the following language-
L(G) = { an b2n | n>=1}
Example 3: Consider the following language-
L(G) = { a2n bn | n>=1}
Example 4: Consider the following language-
L(G) = { an bm an| n, m >= 1}
Example 5: Find out the grammar correspond to following language-
L(G) = { ai bm cm| m >= 1, i>=0}
solution: Grammar corresponding to above language are-
S -> aS | A
A -> bAc | bc
since there is no relation between i and m. so first of all, we have inserted number of a's using S -> aS production rule.
also the above language will generate strings that contains number of b's and c's only. so we have used S -> A production rule. and for number of b's and c's in equal manner, we have used A -> bAc | bc production rules.
Example 6: Find out the grammar correspond to following language-
L(G) = { am bm ci| m >= 1, i>=0}
Example 7: Find out the grammar correspond to following language-
Solution: Grammar corresponding to above language are
S -> aSa | bSb | c
since the above language also contains null so we have used S -> c production.
also w contains all the string of 0's and 1's and wT contains all the string of 1's and 0's ( wT means transpose of w). so we have used productions -
S -> aSa | bSb.
Example 8: Let L be the set of all palindrome strings over (0, 1). Construct G generating L.
Solution : Grammar (G) corresponding to above language are-
S -> ^
S -> 0 S -> 1
S -> 0S1 S -> 1S1
since ^ , 0 and 1 are single terminals. and single terminals always a palindrome string. so we have used S -> ^ S -> 0 S -> 1 production rules.
also for other strings of 0's and 1's, we have used production rules S -> 0S0 and S -> 1S1.
Example 9: Construct a grammar generating {am bm cm | n>=1 }
Solution: Grammar (G) corresponding to above language are-
S -> aSAc | abc
cA -> Ac
bA -> bb
other good examples, I will cover later.
No comments:
Post a Comment