COSC1107/1105 Computing Theory
School of Computing Technologies Semester 2, 2021
Tutorial No. 2: Languages & Grammars
Before this tutorial you are expected to have read Section 3 of the Computing Theory notes.
The aim of this tutorial is to gain some experience with regular expressions and context-free grammars. You will also gain some experience with generating parsers from context-free grammars. By the end of this tutorial you should be able to analyse a given grammar, and generate a grammar to meet a given specification.
Also you should be able to generate a parse tree from a given grammar and string and identify ambiguities in grammars. You may not complete all questions below during the tutorial, but you are expected to complete them later by yourself.
PART1: RegularExpressions……………………………………………………………………
(a) Given that a language is basically a set of strings (or words), state the language obtained when intersecting L1 and L2 in the following cases:
i. L1 ={ancmdn | n,m≥0}withL2 ={c}∗ Solution: L1 ∩ L2 = {cn | n ≥ 0}.
ii. L1 ={ancmdn | n,m≥0}withL2 ={b}∗ Solution: L1 ∩ L2 = {ε}.
iii. L1 ={1n2m | n,m≥0,niseven,andmisodd}withL2 ={3}∗ Solution: L1 ∩ L2 = ∅.
iv. L1 ={1n2m | n,m≥0,niseven,andmisodd}withL2 ={1}·{2}∗ Solution: L1 ∩ L2 = ∅.
v. L1 ={1n2m | n,m≥0,niseven,andmisodd}withL2 ={1}∗ ·{2}∗
Solution: L1 ∩L2 ={1n2m |n,m≥0,niseven,andmisodd}=L1,becauseL1 ⊂L2.
vi. L1 ={1n2m | n,m≥0,niseven,andmisodd}withL2 ={ε,1,11}·{2}∗ Solution: L1 ∩L2 ={1n2m |n∈{0,2},m≥0, andmisodd}.
(b) Determine if each of the following strings belongs to the corresponding regular language. i. ‘10100010’ and L((0∗10)∗).
ii. ‘011100’ and L((0 + (11)∗)∗).
Solution: No. There is no way to produce odd number of 1s
iii. ‘000111100’ and L(((011 + 11)∗(00)∗)∗).
Solution: Expand (0∗10)∗ three times. For the first two expansion, resolve 0∗ to empty string. In the third step, 0∗ will resolve to 00
Solution: Expand the outermost Kleene star from ((011 + 11)∗(00)∗)∗ three times. First time, expand only (00)∗. Second time, choose 011 from (011 + 11)∗ and expand once. In the last expansion, choose 11 from (011 + 11)∗ expanding once and expand (00)∗ once.
1
COSC1107/1105 – Computing Theory Tutorial 2: Languages & Grammars Page 2 of 10 iv. ‘011100101’ and L(01∗10∗(11∗0)∗).
Solution: No. There is no way to end the string with a 1, once 0∗ has been expanded.
We use w1 + w2 or w1 | w2 to denote the alternation operation (w1 or w2), and w+ to denote ww∗ (one or more
repetitions of w).
(c) Find regular expressions denoting each of the following languages:
i. The language of strings belonging to {0, 1}∗ that start with 0 and end with 1. Solution: 0(0 + 1)∗1.
ii. Thelanguage{101,1001,10001,100001,…}. Solution: 100∗1.
(d) Let S = {aa, ab, ba, bb}. Provide at least two alternative descriptive definitions for language S∗.
Solution: There are many ways of describing the language S∗. Some examples are:
• S∗ = {w | w = w1w2 ···wn,n ≥ 0,wi ∈ {aa,ab,ba,bb}}
• S∗ = {w | w is string built from a’s and b’s of even length}
• S∗ ={w|w∈{a,b}∗,|w| mod2=0}
• S∗ = {ε,aa,ab,ba,bb,aaaa,aaab,…,bbbb,aaaaaa,…}
• S∗ =L((aa+ab+ba+bb)∗)
• S∗ =L(((a+b)(a+b))∗)
• S∗ = L(G), where G is the regular grammar:
A → aa | ab | ba | bb | AA | ε
• S∗ = L(G), where G is the regular grammar:
A → aB | bB | ε
B → aA | bA
• S∗ = L(G), where G is the context-free grammar:
A → aAa | aAb | bAa | bAb | ε
• S∗ = L(M), where M is the finite state machine:
q0
a,b a,b
q1
(e) Which of the following languages can be represented by regular expressions? (A ‘yes’ or ‘no’ answer will suffice, you do not need to give the regular expression)
i. The set of all words contained in {0, 1}∗ that have an even number of 0’s and an odd number of 1’s. ii. The set of all words contained in {0, 1}∗ whose lengths are divisible (i.e., with no remainder) by 3.
iii. The set of all words contained in {0, 1}∗ that do not contain ‘101‘ as a substring. iv. The set of all words with the same number of 0’s and 1’s.
Solution: All but the last one. The question only asks you to give a true/false answer. For the most part, these regular expressions are very ugly and cumbersome, and we don’t expect you to give them; this question is more testing your knowledge about the expressive power of the different ways of representing languages. Some students have trouble accepting the fact that some of these languages can be represented as regular expressions, because they are unable to find the regular expressions yourselves. So here is an example for the first one, to give you a sense of how ugly representing languages as regular expressions can be compared to other representations.
We can represent the given language as a DFA like this:
RMIT CT 2021 (Semester 2) – Exercise 1 continues on the next page. . .
COSC1107/1105 – Computing Theory Tutorial 2: Languages & Grammars Page 3 of 10
qee
qoo
Here the label qee means that, in this state, we have an even number of 0’s and an even number of 1’s; qoe means that, in this state, we have an odd number of 0’s and an even number of 1’s, and so on. The final state is qeo, where we have an even number of 0’s and an odd number of 1’s (as acceptance into the language requires) and is denoted by a double circle. The initial state (even 0’s, even 1’s) is denoted by an arrow. Starting at the initial state, we can trace any string we like following the transitions, and if at the end of the string trace we end up in state qeo, that means the word is accepted as a member of the language; if not, then it is rejected.
But what has all of this got to do with regular expressions, though? I hear you ask..
Regular expressions and finite state automata have the same expressive power; that is, anything that can be represented as a finite state automata can be represented as a regular expression, and vice-versa. There are a number of algorithms that can be used to convert between FSA’s and regular expressions (some of them are detailed [here]), but you can also just build the FSA in JFLAP and then use the convert tool to give you the regular expression. This is the result you get from converting it using JFLAP:
((0(11)∗0)∗(1 + 0(11)∗10)(00 + 01(11)∗10)∗(1 + 01(11)∗0))∗(0(11)∗0)∗(1 + 0(11)∗10)(00 + 01(11)∗10)∗
Pretty ugly, huh? So while you may have trouble building the actual regular expressions themselves, this question is asking you to think about the expressive power of regular expressions. Even though the expression may be really long and cumbersome, if there is no need to keep track of exactly how many of each character is in each string, then it can be expressed as a regular expression or FSA. When you need to keep track of how many of each character, then you may need something with greater expressive power.
Thanks to tutor for developing this full answer!
qeo
qoe
(f) Let L be the language defined over alphabet {a, b} and containing all strings whose length is divisible (i.e., with no remainder) by 3. Find a set S such that S∗ = L.
PART 2: Grammars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Examples:
1. Use set notation to define the language of the grammar below.
S →aS |aA|c A → Ab | ε
Solution: In order to determine the language of the grammar, consider all possible derivations from S. Initially, we can use the first rule (S → aS) an arbitrary number of times. Eventually we choose either c and stop, or aA. In the first case, the string generated is aic for some i ≥ 0. In the second case, we have ai+1A (it is i + 1 rather than i due to the rule being S → aA rather than S → A).
Now from A we can get Ab, and then Abb and Abbb and so on, until eventually we choose A → ε and we stop. Hence from A we can get bj for some j ≥ 0. Note that as this is independent of the number of as generated by the rule for S, we use a new variable j rather than reusing i.
Hence the language of this grammar is {aic | i ≥ 0} ∪ {ai+1bj | i,j ≥ 0}, or equivalently {aic | i ≥ 0} ∪ {aibj | i ≥ 1, j ≥ 0}.
2. Use set notation to define the language of the grammar below.
Solution:
S = {aaa, aab, aba, abb, baa, bab, bba, bbb} or
S={w|w∈{a,b}∗, |w|=3}
RMIT CT 2021 (Semester 2) – Exercise 2 continues on the next page. . .
1
1
1 1
0
0
0 0
COSC1107/1105 – Computing Theory Tutorial 2: Languages & Grammars Page 4 of 10
Let G be the grammar
S → aaSB | aaB B → bB | b
Solution: The set notation is used to describe the strings that may be produced or accepted by this grammar. From the second rule of the grammar, the B rule can be replaced with either a single b or bB. Thus, the B rule can be expanded to any number of bs, greater than zero. The first rule states that valid strings (S) begin with aa, consist of S expanded, and finish with the B rule. Thus, for every two as that are in the string, there must be at least one b at the end.
Therefore, the set notation of this grammar is {a2i bj | j ≥ i, i ≥ 1}
3. Construct a grammar over {a, b} which recognises the language {ai b2i | i ≥ 1}
Solution: There are various ways to tackle problems like this one. One way is to start with the shortest possible string, and then the next shortest, and then the next, until you see a pattern. Then write down the pattern as a rule. In this case, the shortest string in the language is abb, the next shortest is aabbbb, the next is aaabbbbbb and the next is aaaabbbbbbbb. One pattern that you may have noticed by now is that to get a longer string, you only need to take shorter one and add a to the front and bb to the end. This suggests the rule S → aSbb, as if S is a valid string, then so is aSbb. Clearly the shortest string must be in the language as well, so we also need S → abb. This gives us the grammar below
S → aSbb | abb
(a) For each of the following grammars, use set notation to define the language generated by the grammar. i. S→aaSB|ε
B → bB | b
Solution: {a2ibj |j≥i,i≥1}∪{ε}
ii. S→aSbb|A A → cA | c
Solution: {aicjb2i | i ≥ 0,j ≥ 1} iii. S→aS|A
A → cA | c | S
Solution: {w ∈ {a, c}∗ | w ends with c}
(b) For each of the following languages, construct a grammar which recognises it. i. {w∈{a,b}∗ |whasoddlength}
ii. {w ∈ {a,b}∗ | w is a palindrome }
iii. {w∈{a,b}∗ |whasnoasbeforebs}
iv. {w∈{a,b}∗ |whas≥3as}
Solution:
S → SSS | a | b OR
S → aA | bA | a | b A→aS |bS
Solution:
S → aSa | bSb | a | b | ε
Solution:
S → bS | A A → aA | ε
Solution:
S →bS |aA A → bA | aB
RMIT CT 2021 (Semester 2) – Exercise 2 continues on the next page. . .
COSC1107/1105 – Computing Theory Tutorial 2: Languages & Grammars Page 5 of 10
B → bB | aC
C → bC | aC | ε OR
S → AaAaAaA A → aA | bA | ε
v. {aibicj |i≥0,j≥1}
vi. {aibjci |i≥0,j≥1}
vii. {aibjcjai | i ≥ 0,j ≥ 1}
PART 3: Regular Expressions & Grammars…………………………………………………….. As well as set notation and grammars, regular expressions can be used to describe strings. The regular expression
(ab | ba)∗
describes strings that contain ab or ba, any number of times, including zero. The ∗ indicates that whatever comes before may occur any number of times, including zero. Within the bracket, ab | ba indicates ab or ba.
Therefore, valid strings include ab, ba, abba, baab, ababab, baabba, etc. . .
(a) In your group, discuss the differences between the regular expressions, (ab | ba)∗, and ((ab)∗ | (ba)∗). (b) For each of the following regular expressions, write a regular grammar that defines the same language.
i. a∗b∗c∗
ii. (a|b|c)∗aa(a|b|c)∗bb(a|b|c)∗ |(a|b|c)∗bb(a|b|c)∗aa(a|b|c)∗
Solution:
S → AC
A → aAb | ε C → cC | c
Solution:
S → aSc | B B → bB | b
Solution:
S → aSa | B B → bBc | bc
Solution:
S → aS | A A → bA | B B → cB | ε
Solution:
A context-free grammar (but not a regular one) is below.
S → AaaAbbA | AbbAaaA
A → aA | bA | cA | ε
A regular grammar for this language is below. S →aS |bS |cS |aA|bE
A → aB
B → aB | bB | cB | bC
C → bD
D → aD | bD | cD | ε
E → bF
F →aF |bF |cF |aG
G → aD
iii. a(a|b|c)∗b(a|b|c)∗a(a|b|c)∗cc
Solution: A context-free grammar (but not a regular one) is below. S → aAbAaAcc
A → aA | bA | cA | ε
RMIT CT 2021 (Semester 2) – Exercise 3 continues on the next page. . .
COSC1107/1105 – Computing Theory Tutorial 2: Languages & Grammars Page 6 of 10
A regular grammar for this language is below.
S → aA
A → aA | bA | cA | bB B → aB | bB | cB | aC C →aC |bC |cC |cD D→c
iv. (b|c|a(b|c))∗(a|ε)
PART4: MoreGrammarProblems………………………………………………………………
(a) Constructagrammarover{a,b}whoselanguagecontainspreciselythosestringswiththesamenumberofasandbs. (Note: you may recall that you were told that it can be proved that such a language cannot be captured by any regular expression. This shows that the set of context-free languages is a strict superset of the set of regular languages.) Valid strings for this question include aabb, bbaa, abab, baab, bbaaab, etc. . .
(b) Construct a grammar over {a,b,c} whose language is {anbmc2n+m | n, m > 0}.
(c) Let G be the grammar:
S → aSaa | B B → bbBdd | C C → bd
i. In English, describe the language of this grammar. The language of the grammar is often referred to as L(G).
ii. How could you alter G so that it accepts the same language except that the number of bs is half the number of ds? (all the other properties should stay the same)
(d) For the following languages, either give a context-free grammar or indicate why this is not possible. i. {aibjck | i,j,k ≥ 0,i ̸= j}
Solution: see (c), but without E-H ii. {aibjck | i,j,k ≥ 0,j ̸= k}
Solution: see (c), but without A-D iii. {aibjck |i,j,k≥0,i̸=jorj̸=k}
Solution:
S → bS | cS | aA | ε | a A→bS |cS
Solution:
ManystudentswouldgetS →aSb|bSa|baS |abS |Sab|Sba|ε
which is close to correct. It won’t allow all the strings in the language though, e.g. aabbbbaa. To correct this, add the rule S → SS to allow concatenation.
This enables simplification to just S → SS | aSb | bSa | ε.
Another solution might be S → SaSbS | SbSaS | ε.
Solution:
S → aScc | aAcc A → bAc | bc
Solution: Any number of as followed by an odd number of bs, followed by the same number of ds as bs, followed by twice the number of as as the first section of as.
Solution: So the language is: any number of as followed by an odd number of bs, followed by double the number of ds than bs, followed by twice the number of as as the first section of as.
S → aSaa | B
B → bbBdddd | bdd
RMIT CT 2021 (Semester 2) –
Exercise 4 continues on the next page. . .
COSC1107/1105 – Computing Theory Tutorial 2: Languages & Grammars Page 7 of 10
Solution:
S → AD | EF
A → aAb | B | C B → aB | a
C → bC | b
D → cD | ε
E → aE | ε
F → bF c | G | H G → bG | b
H → cH | c
iv. {aibjck |i,j,k≥0,i̸=jandj̸=k}
v. {aibjck |i,j,k≥0,i=jorj=k}
vi. {aibjck |i,j,k≥0,i=jandj=k} Solution: Impossible.
(e) Reflection: What use are grammars which do not have recursive rules? Are context-free grammars more powerful than regular expressions?
PART 5: Parse Tress and Derivations……………………………………………………………. Examples:
Let G be the following grammar:
S → AB
A → aA | Aa | a B → bB | Bb | b
1. Using this grammar, produce one left-most derivation, one right-most derivation, and one derivation that is neither left-most nor right-most for the string aaabb.
Solution: A left-most derivation is one in which the left-most variable is used for expansion at all points in the derivation. In other words, when there is a choice to be made between two or more variables, the left-most one is always chosen. A right-most derivation is defined similarly, i.e., that the right-most variable is always chosen. If there is only one variable at every derivation step, then the derivation is both left-most and right-most. See Chapter 3 in Sudkamp’s course book (page 71 in 3rd edition; page 60 in 2nd edition) for definition of left- most derivations.
A left-most derivation for aaabb: S ⇒ AB ⇒ aAB ⇒ aAaB ⇒ aaaB ⇒ aaaBb ⇒ aaabb
A right-most derivation for aaabb: S ⇒ AB ⇒ ABb ⇒ Abb ⇒ aAbb ⇒ aAabb ⇒ aaabb
A derivation that is neither left nor right most: S ⇒ AB ⇒ ABb ⇒ aABb ⇒ aAaBb ⇒ aAabb ⇒ aaabb
2. Build the parse trees for the derivations just obtained.
Solution: All the three derivations have the same parse trees as shown below 3.1.5b: Notice that if you follow the leaf nodes from left to right you will obtain the derived string.
3. Is this grammar ambiguous? Why or why not?
Solution: Impossible. Try seeing if you can do it with context added to your rules, for example rules with multiple symbols on the left-hand-side: Aa → aaa, Ab → bbb.
Solution:
S → AB | CD A → aAb | ε B → cB | ε
C → aC | ε
D → bDc | ε
RMIT CT 2021 (Semester 2) – Exercise 5 continues on the next page. . .
COSC1107/1105 – Computing Theory
Tutorial 2: Languages & Grammars
Page 8 of 10
S AB
a
a
Solution: If you can have two left-most derivations for the same string from a given grammar then that grammar is ambiguous. Please see Sudkamp’s book section on left-most derivations and ambiguous grammars: Definition 3.5.2 in 3rd edition or Definition 4.1.2 in 2nd edition.
Consider the left-most derivation: S ⇒ AB ⇒ AaB ⇒ aAaB ⇒ aaaB ⇒ aaaBb ⇒ aaabb
This is a different left-most derivation for string aaabb than the one shown above (see second step in derivation). Hence grammar G is ambiguous. Compare the parse tree of this derivation (shown below) with the parse tree from Question 2.
S AB AaBb
a
a
A
Ab
4. Give a regular expression for the language of this grammar.
Solution: If you look at the grammar carefully you will see that this language can have one or more as at the begin- ning of the string and one or more bs at the end of the string. Eventually all As are replaced with as and all Bs are replaced with bs. In a regular expression: aa∗bb∗ (or what is equivalent a+b+).
5. Can you give an unambiguous grammar G′ for this grammar? Solution: An unambiguous grammar G′ for this language would be:
S → AB
A → aA | a B → bB | b
Note that L(G) = L(G′) and that there is no word w that can be obtained from two different left-most derivations from G′.
(a) Let G be the grammar S →aS |Sb|ab|SS
i. Using this grammar, produce two leftmost derivations of the string “aaabbb”.
ii. Build the parse trees for the two derivations produced.
Solution: Two such derivations are:
S ⇒aS ⇒aaS ⇒aaSb⇒aaSbb⇒aaabbb and
S ⇒Sb⇒Sbb⇒aSbb⇒aaSbb⇒aaabbb
RMIT CT 2021 (Semester 2) – Exercise 5 continues on the next page. . .
COSC1107/1105 – Computing Theory Tutorial 2: Languages & Grammars Page 9 of 10
Solution:
Derivation 1: Derivation 2:
SS SSb
SSb Sb aS
Sb aS ab ab
a
a
iii. Were there any variations in the answers derived by your group? Compare answers within the group.
iv. If you find the above grammar to be ambiguous, construct an unambiguous grammar equivalent to G; otherwise justify why it is unambiguous.
Solution: Thereshouldbevariationspossiblehere,asyoucanalternatebetweengeneratingasandgenerating bs at any stage.
Solution: It is ambiguous precisely because of the reason stated in the previous question. If you can work out a way to force an order of generating as and bs (e.g. as first, bs second), you can remove the ambiguity.
S → AB | SS
A → aA | a
B → bB | b
In this, because we are either doing a left-most or right-most derivation, we must expand either the A or B rule first. From either of these rules, there is no way to get back up to the S rule, so we cannot decide to expand bs after deciding to expand as.
Another answer could be:
S → SA | A
A → aA | aB
B → bB | b
This version will always expand as before bs regardless of a left-most or right-most derivation (which doesn’t make it better, it’s just a different way of seeing it).
v. Give a regular expression for L(G). Discuss your answer and how it relates to ambiguity.
(b) Let G be the grammar S →aS |aA|a
A → aAb | ab
i. Is it possible to produce a rightmost and a leftmost derivation of the string “aaaabb”? Explain. (Add top-down and bottom-up parsing as well)
Solution: (aa∗bb∗)(aa∗bb∗)∗. In this regular expression, the as are generated before the bs (simply because the as are written before the bs and there is no way to generate them differently).
Another way of writing this is (a+b+)+, where w+ is an abbreviation for ww∗.
Solution: Top down:
S ⇒aS ⇒aaA⇒aaaAb⇒aaaabb Bottom up:
aaaabb
aaaabb
aaaabb
RMIT CT 2021 (Semester 2) – Exercise 5 continues on the next page. . .
COSC1107/1105 – Computing Theory Tutorial 2: Languages & Grammars Page 10 of 10
aaaabb
aaaabb ⇒ aaaAb aaaAb ⇒ aaA aS ⇒ S
Note that here the left-most is the right-most
ii. Build the parse trees for the derivations found.
Solution:
S a
S a
A Ab
b
a
a
iii. Were there any variations in the answers derived by your group? Compare answers within the group.
Solution: It is unlikely that your other group members had different answers.
iv. If you find the above grammar to be ambiguous, construct an unambiguous grammar equivalent to G; otherwise
justify why it is unambiguous.
v. Give a regular expression for L(G).
Solution: Impossible. See rule A → aAb = aibi. This is only possible in a context free grammar.
(c) Let G be the grammar
S → aSb | aAb A → cAd | B B → aBb | ε
As a group activity, take a piece of A4 paper and pass it around the group, each individual carrying out one step of the derivation (leftmost or rightmost) to construct a parse tree, on the following strings :
i. “aacabdbb”
ii. “aaaaabbbbb”
See if any of the above strings can be derived by more than one parse tree.
(d) Reflection: What is the significance of having more than one parse tree? How is this relevant to compilation issues?
End of tutorial worksheet
Solution: It appears to be unambiguous, since we couldn’t find alternative derivations. This is not a proof, however, but a good indication.
Solution: S ⇒ aSb ⇒ aaAbb ⇒ aacAdbb ⇒ aacBdbb ⇒ aacabdbb. Not possible with more than one parse tree.
Solution: S ⇒ aSb ⇒ aaSbb ⇒ aaaSbbb ⇒ aaaaAbbbb ⇒ aaaaBbbbb ⇒ aaaaaBbbbbb ⇒ aaaaabbbbb. There are at least 5 possible derivations.
RMIT CT 2021 (Semester 2) –