ITS64304 Tutorial – 1: Language and Grammar 1
Bachelor of Software Engineering (Hons)
Bachelor of Computer Science (Hons)
ITS64304: Theory of Computation
Tutorial – 1: Language and Grammar
Aim
The aim of this tutorial is to learn regular and context free grammar. By the end of this tutorial,
you should be able to analyze and construct grammars for a given specification and determine the
language for a given grammar. (Aligns with Module Learning Outcome 1)
Taylor’s Graduate Capabilities (TGCs) developed
1.1 Grammars
Examples
1) Construct a grammar over {a, b} that recognizes the language {aib2i | i ≥ 1}
Solutions
1) Start writing the shortest possible string followed by the next shortest and so on, until you
could see a pattern. The pattern seen could be then written as a rule.
The shortest string possible in this case is abb, then aabbbb, then aaabbbbbb and so on. You
repeat a once and b twice every time. This could be written as S → aSbb, and we also need S
→ abb. Hence the grammar for the above question could be written as,
S → aSbb | abb
ITS64304 Tutorial – 1: Language and Grammar 2
Questions
1. For each of the following languages, construct a grammar that recognizes it.
a) {w {a, b}* | w has even length}
b) {w {a, b}* | w has odd length}
c) {w {a, b}* | w has b’s followed by a’s}
d) {w {a, b}* | w has ≥ 3b’s}
e) {anbn | n ≥ 0}
f) {anbn cm| n ≥ 0, m ≥ 1}
g) {ambn cm| m ≥ 0, n ≥ 1}
2. For each of the following Regular Expressions, write a regular grammar that defines the
same language
a) a*b*c*
b) (a υ b υ c)* a(a υ b υ c)* b(a υ b υ c)* υ (a υ b υ c)* b(a υ b υ c)* a(a υ b υ c)*
c) a(a υ b υ c)* b(a υ b υ c)*
Reflection
Are Context Free Grammars more powerful than regular expressions? In the tutorial summary
sheet record you answers and observations.
-oo0oo-