Derivations

Derivations

AU May-10,11,12,16, Dec.-11,14,16,17,18, Marks 16

The production rules are used to derive certain strings. We will now formally define the language generated by grammar G = (V, T, P, S). The generation of language using specific rules is called derivation.

Definition :

Let G = (V, T, P, S) be the context free grammar. If A →ẞ is a production of P and a and y are any strings from non-terminals or terminals i.e. in (VUT)* then a Ay → aẞy.

Suppose a₁, a₂, a₃,... a_m are strings in (VUT)*, m ≥ 1.

a₁ ⇒ a₂

a₂ ⇒ a₃

.

.

a_m-1 ⇒ a_m

Then we can say that a₁ ⇒ a_m

The language generated by G is denoted by L(G). The language L is called context free language CFL if L(G) is for CFG.

For example

G = ({S, B} {a, b}, {S → a B b, S)

B → bbb}

is a grammar. Then we can derive a string abbbb as -

i) We will first start from start symbol S

S ⇒ a B b

ii) Then we will replace B by bbb

S ⇒ a B b ⇒ a bbbb

Thus we can obtain the desired language L by certain rules. The language L can be described as a language which starts with letter a and having 4 b's following. Let us solve some examples for derivation of CFG.

Solved Examples

Example 3.3.1 Try to recognize the language L for given CFG.

G = [{S}, {a,b}, P, {S}]

where P = {S → aSb, S → ab}

Solution: Since S  → a S b | a b is a rule. | indicates the 'or' operator.

S  → a S b

If this rule can be recursively applied then,

   S

a S b

   ↓

a a S b b

   ↓

a a a S b b b

and if finally we can put S→ ab then it becomes aaaa bbbb. Thus we can have any number of a's first then equal number of b's following it. Hence we can guess the language as {L=aⁿ bⁿ where n≥1}. The only way to recognize the language is to try out various strings from the given production rules. Simply by observing the derived strings, one can find out the language getting generated from given CFG.

Example 3.3.2 Construct the CFG for the regular expression (0+1)*

Solution: The CFG can be given by,

P = {S → 0S | 1S

S → ε}

The rules are in combination of 0's and 1's with the start symbol. Since (0+1)* indicates (ε, 0, 1, 01, 10, 00, 11, ...) in this set ε is a string. So in the rules we can set the rule S → ε.

Example 3.3.3 Construct a grammar generating

L = w c w^T where we w ϵ {a,b}*

Solution: The strings which can be generated for given L is {aacaa, bcb, abcba, bacab ...}

The grammar could be

S → a S a

S→ b S b

S → c

Since the language L = w c w^T where w ϵ (a + b)*

Hence S → a S a or S → b S b. The string abcba can be generated from given production rules as

S

a S a

a b S b

a b c b a

Thus any of this kind of string could be derived from the given production rules.

Example 3.3.4 Construct CFG for the language L which has all the strings which are all palindrome over Σ = {a,b} AU: Dec.-17, Marks 7

Solution: As we know the strings are palindrome if they posses same alphabets from forward as well as from backward.

For example, the string "madam" is a palindrome because

Since the language L is over = (a, b). We want the production rules to be build a's and b's. As ε can be the palindrome, a can be palindrome even b can be palindrome. So we can write the production rules as

G = ({S}, {a, b}, P, S)

P can be

S → a S a

S → b S b

S → a

S → b

S → ε

The string abaaba can be derived as

which is a palindrome.

Example 3.3.5 Construct CFG for the language containing all the strings of different first and last symbols over Σ = {0,1}.

Solution: Since the problem statement says as if the string starts with 0 it should end with 1 or if the string starts with 1 it should end with 0.

S → 0 A 1 | A 0

A → 0 A | 1 A | ε

Thus clearly, in the above CFG different start and end symbols are maintained. The non terminal A → 0A | 1A | ϵ indicates (0+1)*. Thus the given CFG is equivalent to the regular expression [0 (0+1)*1+1(0+1)*0]

Example 3.3.6 Construct the CFG for the language L= aⁿ b²ⁿ where n ≥ 1.

Solution: Here the number of b's are doubled than a's so we can write

S → aSbb | abb

It is as simple as this!

Example 3.3.7 Build a CFG for the language L = {0ⁱ 1^j 2^k | j>i+k}.

Solution: As the language L = 0ⁱ 1^j 2^k such that j > i + k.

Hence we can rewrite L as

We can again rewrite L for simplification as –

A → 0 A 1 | ε

B → 1 B | 1

C → 1 C 2 | ε

Hence the CFG can be

S → A B C

A → 0 A 1 | ɛ

B → 1 B | 1

C → 1 C 2 | ε

Example 3.3.8 Build a CFG for the language L = {0ⁱ 1^j 2^k | i = j}

Solution: As i = j and there is no condition on k. We can say that k is an arbitrary value. Then we rewrite L as

L = 0ⁱ 1^j 2^k

0ⁱ 1^j = A

2^k = B

S → A B

A → 0 A 1 | ε

B → 2 B | ε

Example 3.3.9 Obtain CFG for the language L = {0ⁱ 1^j 2^k | j≤ k}.

Solution: Here j≤ k. That means the language L has two variations.

L₁ = 0ⁱ 1^j 2^j where k = j

L₂ = 0ⁱ 1^j 2^k where k > j

Hence the required CFG can be

S → A B

A → 0 A | ε

B → 1 B 2 | C

C → 2 C | ε

Example 3.3.10 Consider the alphabet A = (a, b) and the language L= {bb, bab, baab, baaab, ...) over A. AU May-10, Marks 16

i) Is A* finite or infinite? Give a brief reason for your answer. [2]

ii) Write down a regular expression that represents the above language L. [4]

iii) Write down a regular grammar which describes the above language L. [4]

iv) Draw the DFA corresponding to the above language L. [6]

Solution: i) The A* is an infinite language, because there are any number of a's in the string and the string is starting and ending with b. This leads to an infinite strings of the language.

ii) The regular expression will be = ba*b.

iii) The regular grammar G = (V, T, P, S) where, V is set of non terminals = {S, X, T}. T is the set of terminals which is (a, b). P is a set of production rules as shown below -

{

S → bX

X → aX|aT|b

T → b

}

S is a start symbol.

This is a right linear grammar because the non-terminal appears at the right end of the rule.

iv) The DFA will be

Example 3.3.11 Construct a CFG for the set {aⁱ b^j c^k | i ≠ j or j ≠ k} As there are two cases i ≠ j or j ≠ k. AU May-11, Marks 6

Solution: Hence the production rules will be

S → R1 R2

R1 → aAbbBC | aaAbBC

R2 → AbBccC | AbbBcC

A → aA | ε

B → bB | ε

C → cC | ε

Example 3.3.12 If S → aSb|aAb, A → bAa, A → ba is the context free grammar. Determine the context free language. AU Dec.-11, Marks 6

Solution: The strings generated by this grammar are (a ba b, aa babb, aaa bbaa bbb, ...) This denotes the language L = {aⁿ b^m a^m bⁿ |n, m≥1}

Example 3.3.13 Find the context free langauge for the following grammars

1) S → aSbs | bSaS | ε

2) S → aSb | ab AU May-12, Marks 10

Solution : 1) Let us derive some strings from given grammar.

From these derivations, we can observe that the derived strings contain equal number of a's and b's. Thus this CFG denotes the language L containing equal number of a's and b's.

2) Refer example 3.3.1.

Example 3.3.14 Construct a context free grammar for {0^m 1ⁿ | 1≤m≤n} AU: Dec.-14, Marks 4

Solution: G = (V, T, P, S) where

V = {S, A}

T = {0, 1}

P is a production rules set. It is given by

S → 0S1 | 0A |01

A → 1A | 1

Example 3.3.15 Construct a CFG for the regular expression (011 + 1) (01). AU May-16, Marks 6

Solution: The production rules are

S → AB

A → X | Y

B → 01

X → 011

Y → 1

Example 3.3.16 Construct a context free grammar for the language.

L = {aⁿ | n is odd} AU: Dec.-16, Marks 6

Solution: The context free grammar G = (V, T, P, S)

Where

V = (S, T)

T = (a)

The S is a start symbol.

The set of production rules P is

P = { S → aT

T → aaT | ε

}

• Simulation for string aaaaa

S

aT

aaaT

aaaaaT

aaaaa

Example 3.3.17 Give the regular expression of the language generated by the context free grammar (CFG) given below:

S → aS | bS | a | b. Convert regular expression to ε - NFA. AU Dec.-18, Marks 7

Solution: We will first draw the FA for given CFG.

The regular expression is

r.e = (a+b)⁺

The NFA with ε is as designed below