Question

a) Give 5 good examples of Regular language.

b) Give 5 good examples of Regular Grammar.

Answer 1

SOL:

a) 5 good examples of regular languages:

1) L={w| w ∈(a+b)* w starts with a}

This is a Regualar language which accepts set of all strings starts with a

L = {a,aa,ab,aab,....}

2) L = {w| w ∈ (a+b)^* |w|%2 ==0}

This a Regular Language which accepts set of all strings whose length is divisible by 2

L = {ε,aa,ab,ba,bb,...}

3) L = {w | w ∈ (a+b)^* n_a(w)=3 starts with b}

This is a regular language which accepts set of all strings which starts with b and contains exactly 3 a's

L = {baaa,babaa,...}

4) L = {w | w ∈ (a+b)^* n_a(w)%2 ==0 and n_b(w)%3==0}

This is a regular language which accepts set of all strings in which no of a's divisible by 2 and no of b's divisible by 3

L = {ε,aabbb,bbbaa,aaaabbb,....}

5) L = { w | w ∈ (a+b)^* 2nd symbol from begining in w is b}

This is a regular language which accepts set of all strings in which second symbol from begining is b

L = {ab,bb,aba,abb,...}

b) 5 Good examples of Regular grammars:

1) S -> aA

A -> a | b | ε

This regular grammar generates set of all strings which starts with a

The strings generated by this grammar are L = {a,aa,ab,aab,....}

2) S -> aS | bS | a

This regular grammar generates set of all strings which ends with a

The strings generated by this grammar are L = {a,aa,ba,aaa,...}

3) S -> Aa | Ab

A -> Bb

B -> Ba | Bb | ε

This regular grammar generates set of strings in which second symbol is b or ending with ba or bb

L = {ba,bb,abb,aba,aba,...}

4) S -> Sa | Sb | A

A -> Bb

B -> Ba | Bb | ε

This regular grammar generates set of all strings which contains b

L = {b,ab,ba,bb,aab,aba,...}

5) S -> Sa | Sb | A

A -> Bbb | Baa

B -> Ba | Bb | ε

This regualar grammar generates set of all strings which contains either aa or bb

L = { aa,bb,abba,aaaa,...}