2
Language and Grammar
2.1 BASIC TERMINOLOGY AND DEFINITIONS
Q. Define symbol, alphabet and string.
Ans. Symbol: A symbol is a user-defined entity.
Alphabet: An alphabet is a finite set of symbols denoted by Σ in automata. Alphabets are a set of symbols used to construct a language. Example, {0, 1} is binary alphabet, {A…, Z, a…z} is the alphabet set for the English language.
String: A string is defined as a sequence of symbols of finite length. A string is denoted by w in automata. Example, 000111 is a binary string.
(Length of a string w is denoted by |w|. For the previous case, |w| = |000111| = 6).
Q. Define Prefix, proper Prefix, Suffix, proper Suffix, and substring in relation to a string.
Ans. Prefix: The prefix of a string is the string formed by taking any number of symbols from the start of the string. Example, let us take a string w = 0111. For the particular string 
, 0, 01, 011, 0111 are prefixes of the string 0111. For a string of length n, there are n + 1 number of prefixes.
Proper prefix: For a string, any prefix of the string other than the string itself is called the proper prefix of the string. Example: For the string w = 0111, the proper prefixes are , 0, 01, 011.
Suffix: The suffix of a string is formed by taking any number of symbols from the last of the string.
Example, let us take a string w = 0110. For the particular string , 0, 10, 110, 0110 are suffixes of the string 0110. For a string of length n, there are n + 1 number of suffixes.
Proper suffix: For a string, any suffix of the string other than the string itself is called the proper suffix of the string. Example: For the string w = 0110, the proper suffixes are , 0, 10, 110.
Substring: A substring of a string is defined as a string formed by taking any number symbols of the string. Example: For the string w = 012, the substrings are , 0, 1, 2, 01, 12 and 012.
Q. Define set and describe with an example.
Ans. Set: A set is a well-defined collection of objects. Objects constructing a set are called elements or members of the set.
Example, L = {2, 4, 6, 8} is a set, where 2, 4, 6 and 8 are elements or the members of the set.
Q. Define union, intersection, difference, Cartesian product, power set, concatenation in relation to set and describe each of these with examples.
Ans. Union: If there are two sets A and B, then their union is denoted by A 
B. Let A = {2, 3, 4} and B = {3, 5, 6}, then A B = {2, 3, 4, 5, 6}. In general, A B = {x|x A or x B}.
Intersection: If there are two sets A and B, then their intersection is denoted by A ∩ B. Let A = {2, 3, 4} and B = {3, 4, 5, 6}, then A ∩ B = {3, 4}. In general, A ∩ B = {x|x A and x B}.
Difference: If there are two sets A and B, then their difference is denoted by A – B. Let A = {2, 3, 4, 5} and B = {3, 4}, then A – B = {2, 5}. In general, A – B = {x|x A and x 
B}.
Cartesian product: If there are two sets A and B, then their Cartesian product is denoted by A × B. A = {2, 3, 4, 5} and B = {3, 4}, then A × B = {(2,3), (2,4), (3,3), (3,4),(4,3), (4,4), (5,3), (5,4)}. In general, A × B = {(a, b)|a A and b B}.
Power set: The power set of set A is a set of all possible subsets of A. Let A = {a, b}, then the power set of A is {(Ø), (a), (b), (a, b)}. For a set of elements n, the number elements of the power set of A is 2n.
Concatenation: If there are two sets A and B, then their concatenation is denoted by AB. Let A = {a, b} and B = {c, d}, then AB = {ac, ad, bc, bd}. In general, AB = {ab|a is in A and b is in B}.
Q. Define reflexive, symmetric, transitive and equivalence relation with examples.
Ans. Reflexive: A relation R is said to be reflexive on a non-empty set R if every element of A is related to itself by that relation R. Let A = {B, C, D}, where B, C and D are brothers. Then the relation brotherhood is a reflexive relation on the set A as {B, C}, {B, D} and {C, D} are all sets of brother.
Symmetric: A relation R is said to be symmetric if for two elements ‘a’ and ‘b’ in X that if a is related to b then b is related to a. Let A be a set of all students in a class. Let R be a relation called classmate. Then we can call R a symmetric relation. If a and b are two students belonging to the set, then a is a classmate of b and b is a classmate of a.
Transitive: Let R be a relation defined on a set A, then the relation R is said to be transitive if for a, b, c A and if aRb, bRc holds good then aRc also holds good.
Let A = {8, 6, 4}, where R is a relation called greater than. If 8 > 6 and 6 > 4 holds good, then 8 > 4 also holds good. Therefore, ‘greater than’ is a transitive relation.
Equivalence relation: A relation R is called an equivalence relation on ‘A’ if R is reflexive, symmetric and transitive.
2.2 GRAMMAR AND LANGUAGE
Q. Define language and grammar. Why are language and grammar needed in computer science?
Ans: To express ourselves to someone, i.e. to communicate with someone, we need some medium. That medium is language. Hindi, English and Bengali all are used to communicate among persons. Therefore, these are languages.
For constructing a language, there are some rules. Without rules, a language cannot exist. These rules are called the grammar for that language. Without grammar, a language cannot exist.
In computer science, to communicate with computer hardware, the user needs some languages for programming purposes. Like C, C++, Java. These are called Programming Language. These languages are used to communicate with the computer and the user. Therefore, they can be called language. For constructing languages, there are some rules to be followed. These rules are called the grammar for that programming language.
Q. Define grammar in the sense of automata. Justify the definition for the English language.
Ans: Grammar consists of four touples.
G = { VN, Σ P, S},
VN is the set of non-terminals
Σ the set of terminals
P the set of production rule and
S the start symbol.
(Non-terminal symbols are those symbols that can be replaced multiple times. Terminal symbols are those symbols that cannot be replaced further.)
Example, let us take a sentence in English:
Bikash goes to college.
This sentence can be represented in grammatical form like this:
<Sentence> → <Subject><Predicate>
<Subject> → <Noun>/<Pronoun>
<Predicate> → <Verb Phase>
<Verb Phase> → <Verb>.<Preposition>.<Noun>
<Verb> → goes/eats/runs
<Preposition> → to/at
<Noun> → Ram/ Hari/ Bikash/College/School
<Pronoun> → I/ We/ He/ She/ They
Here,
VN : {<Sentence>, <Subject>, <Predicate>….}
Σ : {Ram, Hari, Bikash, He, She…etc.}
P : The production rules given above.
S : <Sentence>
2.3 CHOMSKY HIERARCHY
Q. What is the Chomsky classification of grammar? Mention the languages produced from each type of grammar. Mention the machine format for each of the languages.
Ans: Chomsky, a linguistic, classified the grammar into four types depending on the productions. These are as follows:
Type 0: Type 0 grammar is a phase structure grammar without any restriction. All grammars are Type 0 grammar.
For Type 0 grammar, the production rules are in the format of
{(Lc)(NT)(Rc)} → {String of terminals or non-terminals or both}
Lc : Left context; Rc : Right context; NT: Non-terminal.
Type 1: Type 1 grammar is called context-sensitive grammar.
For Type 1 grammar, all production rules are in the format of context sensitive if all rules in P are of the form
αAβ→αγβ,
where A NT (i.e. A is a single non-terminal), α, β (NT Σ)* (i.e. α and β are strings of nonterminals and terminals) and γ e (NT Σ)+ (i.e. γ is a non-empty string of non-terminals and terminals).
Type 2: Type 2 grammar is called context-free grammar. In the left-hand side of the production, there will no left or right context.
For Type 2 grammar, all the production rules are in the format of
(NT) → α,
where |NT| = 1 and α (NT T)*, NT is non-terminal and T is terminal.
Type 3: Type 3 grammar is called regular grammar. Here all the productions will be in the following forms:
A → α or A → αB,
where A, B NT and α T.
The Chomsky classification is called the Chomsky Hierarchy. This can be represented diagrammatically
From this diagrammatical representation, we can say that all regular grammars are context-free grammar. All context-free grammar are context-sensitive grammar. All context-sensitive grammar are unrestricted grammar.
Q. Give the languages and machine format for different grammars.
Ans:
| Grammar | Language | Machine Format |
| Type 0 | Unrestricted Language | Turing Machine |
| Type 1 | Context-sensitive Language | Linear-bounded Automata |
| Type 2 | Context-free Language | Push Down Automata |
(The null alphabet is represented by 
. The null string is represented by Λ. The null set is represented by Φ.)
2.4 EXAMPLES
Q. Construct the language generated from the given grammar.
S→ aSb/
Ans: (Grammar can be represented in the form of only Production Rules. In the production rule all are given. Considering the previous grammar as example.
VN : {S}
Σ : {a,b}
P : The above given production rules.
S : {S}
)
S → aSb and S → are combined into a single production. S is the start symbol. S is also a non-terminal symbol. Therefore, S can be replaced. S can be replaced by two types of strings, aSb and . In aSb, there is a non-terminal symbol S. Therefore, aSb is not in the language set produced from the grammar. will be in the language set.
In aSb there is a non-terminal S. Therefore, S can be replaced by either or aSb. If S is replaced by it will be ab, which consists of only terminals. Therefore, ab belongs to the language set.
Therefore the language will be anbn, where the value of n will be 0, 1, 2,…n.
[n = 0 means a0b0 means there is no a and no b in the string means null string (Λ).]
Therefore, the language generated from the grammar will be
L(G) = anbn, n≥ 0
This is denoted by the following diagram. (If the grammar was S → aSb/ab, the language will be L(G) = anbn, n > 0.)
Q. Construct the language generated by the given grammar:
S → aCa
C → aCa/b
In the language generated by the grammar, there will be at least one a. Null does not belong to the language set.
The language generated by the grammar L(G) = anban, n > 0
Q. Construct the language generated by the grammar
S → AbB
A → aA/b
B→aB/a
In the language set generated by the grammar, there will be at least one a in both the sides of b. However, it may or may not be possible that in both the sides of b, A and B are replaced in the same number because they are different non-terminals. So, there are most chance to get different number of ‘a’ in both sides. Therefore, the language generated by the grammar is
L(G = anbam, m, n > 0
Q. Construct the language generated from the given grammar:
S → aS /bS/
Ans: In this production rule, there are three productions S → aS, S → bS and S → . In there is no non-terminal, so in the language set there is a null string (Λ). S can be replaced by aS, bS or . If S is replaced by aS in aS, it will be aaS. If S is replaced by bS, it will be abS. If S is replaced by aS in bS, it will be baS. If S is replaced by bS in bS, it will be bbS. If S is replaced by in aS and bS, it will be a and b, respectively, which will belong to the language set. By this process, we will get aa, bb, ab, ba,…, aba, bab…abaaba,…etc.
In a single statement, we can represent the language set as “Any combination of a, b including null.”
In mathematics, it is represented as L(G) = {a, b}*
(Any combination of a, b excluding null will be represented by {a, b}+.)
Q. Construct the language generated from the given grammar.
S → aSa/bSb/C (C is also a terminal symbol.)
Ans: From the start symbol, C is generated, which is a terminal symbol. Therefore, C belongs to the language set. From S, two other production rules are generated aSa and bSb. In aSa, there is a nonterminal S. Therefore, S can be replaced by aSa or bSb or C. If S is replaced by these production rules, the strings will be aaSaa, abSba and aCa, respectively. Similarly, for bSb the strings will be baSab, bbSbb and bCb. Among these, aCa and bCb will be in the language set generated from the grammar.
By this process, we will get aaCaa, abCba, baCab, bbCbb…abaCaba,…, ababbCbbaba like this.
If we look into the string, we will see that before C there is any combination of a and b including [for the string C, there is no a and no b] and after C the string is the reverse of the previous string. If we take the string before C as W, the string after C will be WR.
The language generated from the grammar will be
L(G) = WCWR,
where W (a, b)*
Q. Construct the grammar for the language an, n > 0.
Ans: The language consists of any number of a. As n > 0, in the language set there is at least one a. The grammar for the language is
S → aS/a.
Q. Construct the grammar for the language (ab)n, n > 0.
Ans: The language consists of any number of ab. [Here we can think of ab as a single character.] The grammar for the language is
S → abS/ab.
Q. Construct the grammar for the language anbn, n > 0.
Ans: From the string, we can say that
(i) The language consists of a and b.
(ii) In the language, a will appear before b.
(iii) Number of a and the number of b are same in any string belonging to the language set.
(iv) In the language, there is no null string.
The value of n is greater than 0. The lowest value of n is 1 here. If n = 1, the lowest length string that is produced from the language is ab. So from the start symbol S, ab is produced in the grammar there will be a production S → ab.
In the language set, there are strings like aabb, aaabbb…, anbn. Each time, one a and one b are added in the string. For n = 1, 2, 3….
It can be thought of as follows: in the middle, there is a non-terminal, which is replaced by adding one a at the left and one b at the right and lastly replacing that non-terminal by ab, which produces aabb, aaabbb….
Therefore, the other production is
S → aSb.
The grammar becomes
S → aSb/ab,
where VN: {S}, Σ: {a, b}, P: S → aSb/ab, S: {S}
Q. Construct the grammar for the language ancibn, n, i ≥ 0.
Ans: From the string, we can say that
i) The language consists of a, b and c.
ii) In the language set, a comes before c, c comes before b.
iii) In the language set, the number of a and the number of b are the same while the number of c may be different.
iv) In the language set, a null string may exist.
In the language set, the number of a and the number of b are the same; that means, each time a and b come simultaneously. For anbn, we have seen that there is a production rule S → aSb. In the string, c will come in between a and b by using the production rule S → Sc/. But if c comes directly from S, then c may come after b, if done like
S → Sc → aSbc → abc
Therefore, abc is produced from the production rule, which does not belong to the language set. c Will not come directly from S. We have to introduce another non-terminal A.
The production rules will be like this
S → aSb/A
A → Ac/
Q. Construct the grammar for the language ancibn, n > 0, i ≥ 0.
Ans: In the language set c may be null as i ≥ 0. However, there will be at least one a and one b. The grammar is
S → aSb/aAb
A → Ac/
Q. Construct the grammar for the language an bncibn, n ≥ 0, i > 0.
Ans: In the language set a and b may be null but there will be at least one c. The grammar is
S → aSb/A
A → Ac/c
Q. Construct the grammar for the language anbnci, n > 0, i ≥ 0.
Ans: In the language set there exist a, b and c. a appears before b and b appears before c. The number of a and the number of b are the same; the number of c may be different. There will be at least one a and one b in the language set. If we look into the string, it will be clear that the string consists of two individual strings anbn and ci. Let anbn is generated from the non-terminal symbol A and ci is generated from the non terminal B. The production rule will be S → AB.
anbn with the condition n > 0 is generated from the production rule A → aAb/ab, where A is the start symbol. And ci with the condition i ≥ 0 is generated from the production rule B → cB/ , where B is the start symbol.
The complete grammar will be
S → AB
A → aAb/ab
B → cB/
Q. Construct a grammar for the language anbn+1, n > 0.
Ans. Here the number of b is one more than the number of a. As n > 0, in the language set there is at least one a and at least two b's (as the number of b is one more than the number of a). By the production S → aAbb, one a and two b's will be added to the generated language set. Now the non-terminal A can be replaced multiple times by the production rule A → aAb to produce anA bn+1 . At last A is replaced by by the production rule A → to produce anbn+1
Therefore the grammar for the language is
S → aAbb
A → aAb/
The grammar can be generated in another way.
By two production rules S → aAb and A → aAb , n number of a and n number of b are produced, where n > 0. At last if A is replaced by b using the production rule A → b, the language set anbn+1 will be produced.
Therefore the grammar for the language will be
S → aAb
A → aAb/b
Q. Construct a grammar for the language anbn + 1, n ≥ 0.
Ans: Here the number of b is one more than the number of a. As n ≥ 0, number of a may be zero but there will be atleast one b in the language set. So, b is in the language set. The single b is produced by the production rule S → b. Using the production S → aSb, n number of a and n number of b are produced. At last step S is replaced by b, using the production rule S → b to produce anbn+1
Therefore the grammar for the language is
S → aSb/b
Taking the previous example in consideration we can write the grammar as follows
S → aAbb/b
A → aAb/e
Q. Construct a grammar generating the language anbnci, where n ≥ 1, i ≥ 0.
Ans: The language consists of two parts anbn where n ≥ 1 and c where i ≥ 0. Therefore, from the start symbol S, we need to take two non-terminals A and B, where A generates anbn with n ≥ 1 and B generates ci with i ≥ 0. The grammar for the language is
S → AB
A → aAb/ab
B → Bc/
Q. Construct a grammar generating the language aibncn, where n ≥ 1, i ≥ 0.
Ans: The language consists of two parts bncn where n ≥ 1 and ai where i ≥ 0. Therefore, from the start symbol S, we need to take two non-terminals A and B, where A generates ai with i ≥ 0 and B generates bncn with n ≥ 1. The grammar for the language is
S → AB
A → Aa/
B → bBc/bc
Q. Construct a grammar generating the language ancibn, where n ≥ 1, i ≥ 0.
Ans: In the language, the numbers of a and b are the same, but the number of c is different. First we need to generate a production rule, which generates anbn with n ≥ 1. In the middle of an and bn there is a non-terminal, which generates ci with i ≥ 0. The grammar for the language is
S → aSb/aAb
A → Ac/
Q. Construct the grammar for palindrome of binary numbers.
Ans: A string that is read from left to right and right to left and gives the same result is called a palindrome. A palindrome can be of two types: odd palindrome and even palindrome. Odd palindromes are those types of palindromes where the number of characters is odd. Even palindromes are those types of palindromes where the number of characters is even.
A null string is also a palindrome. The palindrome will consist of ‘0’ and ‘1’. A string will be a palindrome if its first and last characters are the same. The character in the nth position from the beginning will be the same character from the nth position from the last. The palindrome can start with 0 and can start with 1. 0 can come after 0 and 0 can come after 1. 1 can come after 1 and 1 can come after 0.
From the previous discussion, the grammar for the even palindrome is
S → 0S0/1S1/ (null string is also a palindrome)
The grammar for the odd palindrome is
S → 0S0/1S1/0/1
By combining the two grammars for even and odd palindromes, the final grammar will be
S → 0S0/1S1/0/1/
Q. Find the grammar for the language anbm, where n ≥ 2, m ≥ 3.
Ans: In the language set there will be at least two a's and three b's. It is not always true that the number of b is one more than number of a, as m and n are different numbers. In the language set all the a's will appear before b so we need to introduce two different non-terminals A and B to generate a string of a and a string of b, respectively. The grammar for the language is
S → aaABbbb
A → 0aA/
B → bB/
Q. Find the grammar for the language 0m1n, where m ≠ n
Ans: According to the condition m ≠ n, two cases are possible.
a) Number of 0 is more than number of 1
b) Number of 1 is more than number of 0.
Consider two start symbols S1 and S2, where S1 generates the language for case a and S2 generates the language for case b.
Case a: The language is in the form 0m1n. It means all 0 will come before 1. The more 0s will also come before 1. Here we can generate a grammar for producing equal number of 0 and 1. Then by considering a non-terminal A the extra 0s are added by production rule A → 0A/0.
Therefore the grammar for case a is
S1 → AS1
S1 → 0S11/
A → 0A/0
Case b: In this case number of 1 is more than number of 0. So, the extra 1s are added at last. The grammar for case b is
S2 → S2B
S2 → 0S21/
B → 1B/1
Case a and Case b can be added by using a common start symbol S and a production rule S → S1/S2. The complete grammar is
S → S1/S2
S1 → AS1
S1 → 0S11/
A → 0A/0
S2 → S2B
S2 → 0S21/
B → 1B/1
Q. Construct the grammar for the language albmcn, where one of l, m, n = 1 and the remaining two are equal.
Ans: In the language set at least one of a, b or c will exist singly. The terminal elements are a and c. If in the language set there is a single a, the production rules are S → aS1 and S1 → bS1c/. If in the language set there is a single c, the production rules are S → S2c and S2 → aS2b/. b is the middle element. For single b in the middle, the production rules are S → aS3c and S3 → aS3c/b. The grammar for the language is
S → aS1/S2c/aS3c
S1 → bS1c/
S2 → aS2b/
S3 → aS3c/b
Q. Construct the grammar for the language 0m1n, where m ≥ 1 and n ≥ 1 and m < n.
Ans: According to the condition there must be alteast one 0 and one 1 in the language set. But number of 0 must be less than number of 1. The extra 1s are added at the last, because the language is in the form 0m1n. Here we can generate a grammar for producing equal number of 0 and 1. Then by considering a non-terminal B the extra 0s are added by production rule B → B1/1
The complete grammar is
S → 0S1/0B1
B → B1/1
Q. Construct the grammar for the language a1bmcn, where l + m = n.
Ans: The total number of a and b are equal to the total number of c. Either the number of a or the number of b may be 1. In that case, the number of c is 1. If the number of a and the number of b is zero, then the number of c is also zero. Therefore, there is production S → ac/bc/. If in the language there is no a, then the number of b is equal to the number of c. This is the same for a language without b. The production rule is S → aSc/bSc. However, in this case there is a chance of a occurring after b. The modified production is S → aSc/bS1c. The total number of a and b is equal to the total number of c; this can be solved if in each occurrence of a or b, one c is added to the language. The production rule for this case is S1 → bS1c/bc/. The grammar for the language is
S → aSc/bS1c/ac/bc/e
S → bS1c/bc/e
Q. Construct the grammar for the language L = {Set of all strings over 0, 1 containing twice as many 0 than 1}.
Ans: The language consists of 0 and 1. In the language set, the number of 0 is twice that of the number of 1. 0 and 1 can occur in any pattern. The grammar for the language is
S → S1S0S0S/S0S0S1S/S0S1S0S
Q. Construct a grammar consisting of an equal number of 0 and 1.
Ans: The grammar for the language is
S → S0S1S/S1S0S/
Q. Construct a grammar that generates all even integers up to 998.
Ans: In even numbers, the right-most number is one of 0, 2, 4, 6, 8. The middle and left-most number is one of 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. We have to generate even numbers up to 998, i.e. 3 digits. Therefore, we have to consider all even numbers of one and two digits also.
Here the production rule S → A1S1 generates the two digits numbers. The production rule S → A1A2S1 generates 3 digits numbers.
Q. Construct the grammar for WWR, where W (a, b)*.
Ans: The string W consists of a and b. W can be a null string also. WR is the reverse string of W. The number of characters in the string WWR will always be even, except the null string. Therefore, the string is nothing but an even palindrome of a and b including the null string. The grammar will be
S → aSa/bSb/
Q. Construct the grammar for the language L = anbnemdm, m, n > 0.
Ans: The total string can be divided into two parts: (a) A string of a and b, where the number of a and the number of b are the same. (b) A string of c and d, where the numbers of c and d are the same.
From the start symbol, there will be two non-terminals A and B, where A will generate anbn and B will generate cmdm. In the language set there will be no null string. Therefore, the grammar will be
S → AB
A → aAb/ab
B → cBd/cd
Q. Construct the grammar for the language L = anemdmb”, m, n > 0.
Ans: In between a and b there is an equal number of c and d. The number of a and the number of b are the same.
Therefore, we have to construct anbn with a non-terminal in between an and bn. From that nonterminal cmdm will be produced. Therefore, the grammar will be
S → aSb/aAb
A → cAd/cd
2.5 CONTEXT-SENSITIVE GRAMMAR
Q. Construct a grammar for the language anbncn, where n ≥ 1.
Ans: It is difficult to construct anbncn. We construct it by the following process:
(a) First we construct anαn.
(b) Then from αn we construct bncn.
From α, generating bncn is difficult, From αn, (bc)n can be constructed. However, (bc)n is not equal to bncn. Introduce a new non-terminal B:
S → Abc/ABSc
BA → AB
Bb → bb
A →a
Q. Construct a grammar for the language xx, where x (a, b)*.
Ans:
Q. Construct a grammar for the language {anbncndn, n ≥ 1}.
Ans:
WHAT WE HAVE LEARNED SO FAR
1. A set of rules for constructing a language is called the grammar for that language.
2. For every programming language like C, C++ and Java there is a grammar.
3. Grammar consists of four touples. G = {VN, Σ, P, S}, where VN is the set of non-terminals, Σ the set of terminals, P the set of production rule and S the start symbol.
4. Chomsky, a linguistic, classified grammar in to four types depending on the productions. The types are Type 0, i.e. unrestricted grammar, Type 1, i.e. context-sensitive grammar, Type 2, i.e. context-free grammar and Type 3, i.e. regular grammar.
5. For each of the grammar, there is a specific language, namely unrestricted language, context-sensitive language, context-free language and regular expression.
6. Unrestricted language is accepted by Turing Machine, Context-sensitive language is accepted by Linear-bounded automata, Context-free language is accepted by Push down automata and Regular language is accepted by Finite Automata.
7. For Type 0 grammar, the production rules are in the format of {(Lc)(NT)(Rc)} → {String of Terminals or Non-terminals or both}, where Lc id the left context, Rc the right context and NT the nonterminal.
8. For Type 1 grammar all production rules are in the format of context sensitive if all rules in P are of the form αAβ → αγβ, where A NT (i.e. A is a single non-terminal), α, β (NT Σ)* (i.e. α and β are strings of non-terminals and terminals) and γ (NT Σ) + (i.e. γ is a non-empty string of non-terminals and terminals).
9. Type 2 Grammar is called context-free grammar. In the left-hand side of the production there will no left or right context. For Type 2 grammar, all the production rules are in the format of (NT) → α, where |NT| = 1 and α (NT T)*, NT is the non-terminal and T the terminal.
10. Type 3 grammar is called regular grammar. Here all the productions will be in the following forms. A → α or A → αB, where A, B NT and α T.
SOLVED PROBLEMS
1. Find the languages generated by the following grammars:
Ans:
The language generated by the grammar is L(G) = anbmambn, where m, n > 0.
The language generated by the grammar is L(G) = 0m1m + n, where m, n > 0.
(c) First let us try to find the expressions generated by B → 0B/1S and A → 1A/1. Then replace the expressions generated by A and B into S → 0A/1B.
2. Generate a CFG for the language L = Alternating sequence of a and b.
Ans: The language may start with a or with b. If the string starts with a, then the language is (ab)n. If the string starts with b, then the language is (ba)n. If the string starts with a, then the production rule is S → aA. If the string starts with b, then the production rule is S → bB. For alternating sequences of a and b, the production rules are A → bB, B → aA, A → b, B → a. The production rules are S → aA, S → bB, A → bB, B → aA, A → b, B → a.
3. Construct a grammar that generates all odd integers up to 999.
Ans: Odd numbers from 0 to 9 are 1, 3, 5, 7, 9. The grammar for generating 1, 3, 5, 7, 9 is S → 1/3/5/7/ 9.
For an odd number of length 2, the grammar is S → AS1, where A → 0/1…7/8/9, S1 → 1/3/5/7/9.
For an odd number of length 3, the grammar is S → BAS1, where A → 0/1…7/8/9, B → 0/1…7/8/9 and S1 → 1/3/5/7/9.
4. Construct a grammar that generates {(01)n (10)n}, where n > 0.
Ans: It consists of two languages, (01)n and (10)n. Both are connected by union. Take A and B, two non-terminals, which generate (01)n and (10)n, respectively. From the start symbol S it goes to A and B. The grammar is
S → A/B
A → 01A/01
B → 10B/10
MULTIPLE CHOICE QUESTIONS
1. Which is correct?
(a) a+ = a* a*
(b) a* = a+ a+
(c) a+ = a* a
(d) a* = a+ a*
2. (a, b)* means———.
(a) Any combination of a, b including null
(b) Any combination of a, b excluding null
(c) Any combination of a, b but a will come first
(d) None of these
3. (a, b)+ means———.
(a) Any combination of a, b including null
(b) Any combination of a, b excluding null
(c) Any combination of a, b but a will come first
(d) None of these
4. What is the language generated by the grammar S → aSb, S → A, A → aA ?
(a) ambm
(b) Ø
(c) anbm
(d) ambm
5. Which type of grammar is the following in particular S → aSb, S → ab ?
(a) Unrestricted
(b) Context-sensitive grammar
(c) Context-free grammar
(d) Regular grammar
6. The language generated by the grammar S → 0S0, S → 1S1, S → 0, S → 1 is———.
(a) Even palindrome of 0 and 1
(b) Odd palindrome of 0 and 1
(c) Any combination of 0 and 1
(d) None of these
7. The language {ambncm + n | m, n ≥ 1} is———.
(a) Regular
(b) Context free but not regular
(c) Context sensitive but not context free
(d) Type 0 but not context sensitive
8. Which type of grammar is the following in particular? A → aB, B → ac, C → bC/aD, D → bA/b
(a) Context-sensitive grammar
(b) Context-free grammar
(c) Context free but regular in particular
(d) Not Type 0 but context free
9. The machine format of context-sensitive grammar is
(a) Finite automata
(b) Push down automata
(c) Linear-bounded automata
(d) All of the above
Ans: 1.c 2.a 3.b 4.b [Because no string of terminal is produced] 5.c 6.b 7.b 8.c 9.c
EXERCISES
1. Find the languages generated by the following grammars:
(a) S → aSb/A, A → Ac/c
(b) S → aSb/aAb, A → Ac/
(c) S → aSb/aAb, A → bA/b
(d) S → S1/S2, S1 → 0S11/0A, A → 0A/, S2 → 0S21/B1, B → B1/
2. Construct grammars for the following languages:
(a) L = (a, b)*, where all a's appear before b
(b) L = (a, b)*, where there are equal numbers of a and b
(c) L = (a, b)*, where the number of b is one more than the number of a
(d) L = (a, b)*, where there is at least one a
3. Construct grammars for the following languages:
(a) L = ambn, where m ≠ n.
(b) L = axbycz, where y = x + z
(c) L = axbycz, where z = x + y
(d) L = axbycz, where x = y + z
4. Construct grammars for the following languages:
(a) {anbn | n > 0} {cmdm | m ≥ 0}
(b) {anbn | n > 0} {amtm | m ≥ 0}
(c) {axbycz, where x = y + z} {L = axbycz, where z = x + y}
5. Construct grammars for the following languages:
(a) L = (0 + 1)* 11 (11)*
(b) L = (Set of all strings of a, b beginning and ending with a)
(c) L = a2n + 1, where n > 0
FILL IN THE BLANKS
1. For a string, any prefix of the string other than the string itself is called as the __________ of the string.
2. For a string, any suffix of the string other than the string itself is called as the __________ of the string.
3. If there are two sets A and B, then their intersection is denoted by __________
4. For a set of elements n the number elements of power set of A is __________.
5. If 2n is the number of elements of the power set of a set then the number of element in the set is __________.
6. A relation R is said to be __________ if for two elements ‘a’ and ‘b’ in X that if a is related to b then b is related to a.
7. A relation R is said to be __________ if for a,b,c e A and if aRb , bRc holds good then aRc also holds good.
8. A relation R is called as an __________ on 'A if R is reflexive, symmetric and transitive.
9. Grammar consists of four touples- Set of Non- Terminals, __________, Set of Production Rule, __________
10. According to Chomsky Hierarchy there are __________ types of grammars.
11. Type 1 Grammar is called __________
12. Type 2 Grammar is called __________
13. According to Chomsky Hierarchy Regular Grammar is Type __________ grammar.
14. All languages are accepted by __________
15. The machine format of Context Free Language is __________
16. Linear Bounded automata is the machine format of __________
17. The machine format of Type 3 language is __________
18. Grammar where production rules are in the format CAB → ay6 is __________ grammar
19. In a Context Free Grammar at the left hand side there is __________ non terminal.
20. Type 3 language is called __________.
21. anbncn is an example of __________ language in particular.
22. The grammar S → aSb/A, A → Ac/c is an example of __________ grammar in particular.
23. The grammar S → Abc/ ABSc, BA → AB, Bb → bb, A ^ a is an example of __________ grammar in particular.
24. The grammar A → aA/bB/a/b, B → bB/b is an example of __________ grammar in particular
25. The language a*(a+b)b* is an example of __________ language in particular.
26. L = Alternating sequence of ‘a’ and ‘b’ is an example of __________ language in particular.
27. Regular Expression is accepted by type __________ grammar.
ANSWERS
1. proper prefix
2. proper suffix
3. AnB
4. 2n
5. n
6. symmetric
7. transitive
8. equivalence relation
9. Set of Terminals, Start Symbol
10. Four
11. Context Sensitive Grammar
12. Context Free Grammar
13. Three
14. Turing Machine
15. Push Down Automata
16. Context Sensitive Grammar
17. Finite Automata
18. Context Sensitive
19. Single
20. Regular Expression
21. Context Sensitive
22. Context Free
23. Context Sensitive
24. Regular Grammar
25. Type 4
26. Context Free
27. Three