COSC1107/1105 Computing Theory
School of Computing Technologies Semester 2, 2021
Tutorial No. 9: Grammars Type 0 and 1
Before this tutorial you are expected to have read Section 9 of the Computing Theory notes. Aim
The aim of this tutorial is to give some insight into the relationships between grammars and automata. By the end of this tutorial you should be able to analyse and generate unrestricted grammars and to recognise what class of grammar or automaton is required for a given language. You should be able to complete all the questions below after this tutorial.
PART1: GrammarsType0andType1………………………………………………………….. (a) What is the Chomsky Hierarchy and why it is important?
Solution:
It is a hierarchy of four formal grammatical systems for describing various classes of languages; as the grammar number increases, the generated language becomes simpler. Each grammar has a corresponding type of automata type.
It is important both for Computer Science, Cognitive Science, and linguistics. For Computer Science, it provides a precise relationship between languages (related to decision problems to solve) and power of computation. So, a decision problem that can be captured with a regular language will require just finite state machine power of computation.
It is also important because it makes you think hard about very abstract ideas, and that is always fun (once you get it!). 😉
(b) Consider the following grammar.
S → a | CD
C → ACB | AB AB → aBA
Aa → aA
Ba → aB
AD → Da
BD → Ea
BE → Ea E→a
i. Give a derivation of the strings aaaa and aaaaaaaaa.
ii. Showthatforanyn≥1wecanderiveS⇒AnBnD
Solution:
S ⇒ CD ⇒ ABD ⇒ aBAD ⇒ aBDa ⇒ aEaa ⇒ aaaa
S ⇒ CD ⇒ ACBD ⇒ AABBD ⇒ AaBABD ⇒ aABABD ⇒ aaBAABD ⇒ aaBAaBAD ⇒ aaBaABAD ⇒ aaaBABAD ⇒ aaaBaBAAD ⇒ aaaaBBAAD ⇒ aaaaBBADa ⇒ aaaaBBDaa ⇒ aaaaBEaaa ⇒ aaaaEaaaa ⇒ a9
1
COSC1107/1105 – Computing Theory Tutorial 7: Grammars Type 0 and 1 Page 2 of 2
Solution:
The rule S → CD puts a D at the end of the string, and the rules C → ACB | AB replace the C with the same number of As as Bs. Then, S ⇒ CD ⇒ ACBD ⇒ AACBBD ⇒ … ⇒ An−1CBn−1D ⇒ AnBnD.
iii. Show that for any n ≥ 1 we can derive AnBnD ⇒ an2 BnAnD
Solution:
The rule AB → aBA can be used like a bubble sort, to move the Bs to the beginning of the string (or alternatively, the As to the end of a string). To move a B to the beginning of the string, it must pass n As. Every time it passes an A, it generates an a. Therefore, each B generates n as while moving to the front. Since this happens for n bs, the total number of as generated is n2.
AnBnD ⇒ An−1aBABn−1D ⇒ An−1aBaBABn−2D ⇒ An−1aBaBaBABn−3D ⇒ . . . ⇒ An−1(aB)nAD ⇒ anAn−1BnAD ⇒ ananAn−2BnAAD ⇒ … ⇒ an2 BnAnD
iv. What is L(G)?
(c) What is L(G) for the grammar below? S → aXY ba
XY →XYbZ|λ Zb → bZ
Za → aa
(d) What is L(G) for the grammar below? S→A
A→aABC |abC cB → Bc
bB → bb
bC → b
(e) Give an unrestricted grammar for the following languages: i. {aibjaibj |i,j≥0}
Solution:
The grammar can either be defined as L(G) = {an2+2n+1 | n ≥ 0} or equivalently, L(G) = {an2 | n > 0}
(these are equivalent, since (n + 1)2 = n2 + 2n + 1).
an2 BnAnD ⇒ an2 BnDan ⇒ an2 Bn−1Eaan ⇒ an2 Ean−1aan ⇒ an2 anaan = a(n+1)2
Solution:
Seems a lot more complex than it is, {abiai | i > 0}.
Solution:
Rule 3 is not useful. {aibi | i > 0}.
Solution:
S → ABZ
A → CAE | ε B → DBF | ε ED → DE FZ → Zb Z→Y
EY →Ya Y→X
DX → Xb X→W
CW → Wa W→ε
ii. {aibicidi | i ≥ 0}
RMIT CT 2021 (Semester 2) –
COSC1107/1105 – Computing Theory Tutorial 7: Grammars Type 0 and 1 Page 3 of 2
Solution:
S → ABCDS | Z DA → AD
CA → AC
BA → AB
DB → BD CB → BC DC → CD DZ → Zd Z→Y
CY →Yc Y→X BX → Xb X→W AW → W a W→ε
iii. {xyz | x,y,z ∈ {a,b}∗}
iv. {www|w∈{a,b}∗}
Solution:
S → XY Z
X → aX | bX | ε Y → aY | bY | ε Z → aZ | bZ | ε
Solution:
Strategy: A1 and B1 generate a’s and b’s for the far left w; A2 and B2 generate a’s and b’s for the middle w, and A3 and B3 generate a’s and b’s for the far right w. We first generate them all. Then we sort them (e.g., A3 and B3 should move to the right of all A1, B1, A2 and B2). Finally, Z3 will move left replacing all A3 and B3 with a’s and b’s respectively; then change to Z2 and do the same for the a’s and b’s of the middle w, and finally change to Z1 to produce the first w.
S → A1A2A3S | B1B2B3S | Z3
B3A1 → A1B3 B3A2 → A2B3 B3B1 → B1B3 B3B2 → B2B3
A3A1 → A1A3 A3A2 → A2A3 A3B1 → B1A3 A3B2 → B2A3
A2A1 → A1A2 A2B1 → B1A2
A3Z3 → Z3a
B2Z2 → Z2b [generate b’s and a’s on the middle w] A2Z2 → Z2a
[move B3 to the far right (b’s the last w)]
[move A3 to the far right (a’s for the last w)]
[move A2 to the middle (a’s for the middle w)]
[move B2 to the middle (b’s for the middle w)] B3Z3 → Z3b [generate b’s and a’s on the far right w]
B2A1 → A1B2 B2B1 → B1B2
RMIT CT 2021 (Semester 2) –
COSC1107/1105 – Computing Theory Tutorial 7: Grammars Type 0 and 1 Page 4 of 2
B1Z1 → Z1b [generate b’s and a’s on the far left w] A1Z1 → Z1a
Z3 → Z2 [convert Z3 to Z2, Z2 to Z1, and finish] Z2 → Z1
Z1 → ε
(f) Let M be the Turing machine below, with final state as q2. δBab
q0 q1 q2 i.
ii.
q1,B,R
q1,a,R q3,b,R
q2,b,R Give a regular expression for L(M ).
(g) Let
Solution:
b(ab)∗
From the Turing machine, construct an unrestricted grammar for L(M ).
Solution:
Basically, the idea is to start from the end of the derivation and finish up at the start of the derivation. So first, we build the string we are trying to derive (beginning with a blank) and then set the final state.
S →> Bh <
h → ah | bh | q2
Then we go backwards through the rules. Note that the head is currently on the character to its right. in other words, in each state, since we are working backwards, we have just read the character to the left. So each grammar rule does the backwards step of the machine rule.
aq1 → q2a
bq2 → q1b
Bq1 → q0B
Now we need to ensure that we can only clear the extra characters if we are in the beginning state and the head is on the first blank, i.e., where the machine starts:
> q0B → ε
<→ ε
For a formal explanation, read page 79 of CT course notes.
Trace the computation of M with input bab and give the corresponding derivation in the grammar.
iii.
G be the grammar S → SBA | a
BA → AB aA → aaB B→b
i. Give a derivation of aaabb.
ii. What is L(G)?
iii. Construct a context-free grammar for this language.
Solution:
Simple to do.
Solution:
Impossible. Can do aabb or aaabbbb, e.g.:
S ⇒ SBA ⇒ SBABA ⇒ SABBA ⇒ SABAB ⇒ SAABB ⇒ aAABB ⇒ aaBABB ⇒ aaABBB ⇒ aaaBBBB ⇒ aaabBBB ⇒ aaabbBB ⇒ aaabbbB ⇒ aaabbbb
Solution:
{ai+1b2i | i ≥ 0}
RMIT CT 2021 (Semester 2) -
COSC1107/1105 - Computing Theory Tutorial 7: Grammars Type 0 and 1 Page 5 of 2
Solution:
S → aSbb | a
(h) Let L be the language {aib2iai | i > 0}.
i. Give an informal reason why L is not context-free.
ii. Construct a context-sensitive grammar for L.
Solution:
It has to count three items, a single stack can only count two (one with pushing, one with popping)
Solution:
S → A1BSDA2 | LR | abba A1 → a
A2 → a
BA1 → A1B A2D → DA2
BL → Lb | Gb A1G → aab
RD → bR | bH HA2 → baa
L will process to left; R move to right each A1 is transformed into an a each A2 is transformed into an a
sort A1’s to the left sort A2’s to the right
move head L to left writing b’s move head R to right writing b’s
iii. Give the derivation of aabbbbaa.
iv. Construct an LBA M which accepts L, i.e. L = L(M).
Solution:
S ⇒ A1BSDA2 ⇒ A1BLRDA2 ⇒ A1GbRDA2 ⇒ aabbRDA2 ⇒ aabbbHA2 ⇒ aabbbbaa
Solution:
Apparently as of page 86 of notes. Can’t think of an easier way of doing this than the way discussed last tute (that is, overwriting an a, then 2 b’s then an a, with a∗).
a/a, L
b/b,L C/C,R B/B,L b/b,R C/C,L
◃ / ◃,R a/A,R b/B,R
q0 q1 q2 q3 q4 q5
B/B,R a/a,R
b/B,R a/C,L
B/B,R
C/C,L
B/B,R q6
A/A, R
q7
The symbols ◃ and ▹ denote the start and end of the input string respectively. If the machine halts in a non-accepting state or on the right-end marker (▹), then the input is rejected.
PART 2: Grammars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
(a) Give any type of grammar (regular, context-free, context-sensitive or unrestricted), as appropriate, for the following languages:
i. {aibjck |i,j,k≥0,i=jandj=k}
Solution:
The strategy here is to generate the A, B and C non-terminals, sort them and then change them to the terminals. S → ABCS | Z
CA → AC
BA → AB
CB → BC CZ → Zc
RMIT CT 2021 (Semester 2) –
COSC1107/1105 – Computing Theory Tutorial 7: Grammars Type 0 and 1 Page 6 of 2
Z→Y
BY →Yb Y→X AX → Xa X→ε
ii. {aibjck |i,j,k≥0,i̸=jandj̸=k}
Solution:
The key insight here is that there must be at least one character of which there is a smaller number than the other two. We can generate A, B and C non-terminals until this smallest number is reached, and then we can branch off into three possiblities. If b has the smallest number, then all we need to do is generate at least one more a and c, but then we don’t care how many of either we generate because i can equal k. If a has the smallest number, then we need to branch off and ensure that there is at least one more b and that the number of c’s is not equal to b’s as well — similar for if c is the smallest number as well.
The grammar for this is below. It starts by generating A, B and C non-terminals until the smallest number is reached, before changing S to either SA (least a’s), SB (least b’s) or SC (least c’s). The rest of the non- terminals are generated as described above, before they are sorted and finally converted into terminals.
S→ABCS|SA |SB |SC SA → BCTA | BUB
TA →BCTA |BUB |CUC SB → ACTB
TB →ACTB |AUA |CUC |Z SC →ABTC |BUB
TC →ABTC |AUA |BUB
UA →AUA |Z
UB →BUB |Z UC →CUC |Z BA → AB
CB → BC
CA → AC CZ → Zc Z→Y
BY →Yb Y→X AX → Xa X→ε
RMIT CT 2021 (Semester 2) –
End of tutorial worksheet