Copyright © 2007 Gradiance Corporation.
Gradiance Online Accelerated Learning
CFG's --- Proofs
1.
Consider the grammars:
G1:S → AB | a | abC, A → b, C → abC | c
G2:S → a | b | cC, C → cC | c
These grammars do not define the same language. To prove, we use a string that is generated by one but not by the other grammar. Which of the following strings can be used for this proof?
a)
ccccccc
b)
abababcc
c)
aba
d)
abab
2.
Let L be the language of all strings of a's and b's such that no prefix (proper or not) has more b's than a's. Let G be the grammar with productions
S → aS | aSbS | ε
To prove that L = L(G), we need to show two things:
We shall consider only the proof of (1) here. The proof is an induction on n, the number of steps in the derivation S =>* w. Here is an outline of the proof, with reasons omitted. You need to supply the reasons.
Basis:
1)
If n=1, then w is ε because _______.
2)
w is in L because _______.
Induction:
3)
Either (a) S => aS =>n-1 w or (b) S => aSbS =>n-1 w because _______.
4a )
In case (a), w = ax, and S =>n-1 x because _______.
5a)
In case (a), x is in L because _______.
6a)
In case (a), w is in L because _______.
4b)
In case (b), w can be written w = aybz, where S =>p y and S =>q z for some p and q less than n because _______.
5b)
In case (b), y is in L because _______.
6b)
In case (b), z is in L because _______.
7b)
In case (b), w is in L because _______.
Some of the steps above have one of the following reasons:
I) "The following two statements are true: (i) if string x has no prefix with more b's than a's, then neither does string ax, (ii) if strings y and z are such that no prefix has more b's than a's, then neither does string aybz."
II) "All n-step derivations of w produce either ε (for n=1) or use one of the productions with at least one nonterminal in the body (for n > 1). In case the production S → aS is used, then w=ax with x being produced by a (n-1)-step derivation. In case the production S → aSbS is used then w=aybz with y and z being produced by derivations with number of steps less than n."
III) "by the inductive hypothesis"
Choose as correct a (STEP, REASON) pair. (I.e., a correct pair means that step STEP is true because of reason REASON.)
(2,II)
(6a,I)
(2,I)
(1,III)
3.
Let G be the grammar:
S → SS | (S) | ε
L(G) is the language BP of all strings of balanced parentheses, that is, those strings that could appear in a well-formed arithmetic expression. We want to prove that L(G) = BP, which requires two inductive proofs:
We shall here prove only the second. You will see below a sequence of steps in the proof, each with a reason left out. These reasons belong to one of three classes:
A)
Use of the inductive hypothesis.
B)
Reasoning about properties of grammars, e.g., that every derivation has at least one step.
C)
Reasoning about properties of strings, e.g., that every string is longer than any of its proper substrings.
The proof is an induction on the length of w. You should decide on the reason for each step in the proof below, and then identify from the available choices a correct pair consisting of a step and a kind of reason (A, B, or C).
Basis: Length = 0.
(1)
The only string of length 0 in BP is ε because ________
(2)
ε is in L(G) because ________
Induction: |w| = n > 0.
(3)
w is of the form (x)y, where (x) is the shortest proper prefix of w that is in BP, and y is the remainder of w because ________
(4)
x is in BP because ________
(5)
y is in BP because ________
(6)
|x| < n because ________
(7)
|y| < n because ________
(8)
x is in L(G) because ________
(9)
y is in L(G) because ________
(10)
(x) is in L(G) because ________
(11)
w is in L(G) because ________
(5) for reason C
(11) for reason A
(1) for reason B
(7) for reason B
4.
We shall consider only the proof of (2) here. The proof is an induction on n, the length of w. Here is an outline of the proof, with reasons omitted. You need to supply the reasons.
If n=0, then w is ε because _______.
S =>* w because _______.
Either (a) w can be written as w=aw' where for w' each prefix has as many a's as b's or (b) w can be written as w=aw'bw'' where for both w' and w'' hold that each prefix has as many a's as b's because _______.
In case (a), w' is in the language because _______.
In case (a), S =>* w' because _______.
In case (a), S =>* w because _______.
In case (b), both w' and w'' are in the language because _______.
In case (b), S =>* w' because _______.
In case (b), S =>* w'' because _______.
In case (b), S =>* w because _______.
For which of the steps above is the appropriate reason "by the inductive hypothesis"?
6a
6b
4a
4b
5.
We shall here prove only the first. You will see below a sequence of steps in the proof, each with a reason left out. These reasons belong to one of three classes:
The proof is an induction on the number of steps in the derivation of w. You should decide on the reason for each step in the proof below, and then identify from the available choices a correct pair consisting of a step and a kind of reason (A, B, or C).
Basis: One step.
The only 1-step derivation of a terminal string is S => ε because ________
ε is in BP because ________
Induction: An n-step derivation for some n>1.
The derivation S =>n w is either of the form (a) S => SS =>n-1 w or of the form (b) S => (S) =>n-1 w because ________
Case (a):
w = xy, for some strings x and y such that S =>p x and S =>q y, where p<n and q<n because ________
w is in BP because ________
Case (b):
w = (z) for some string z such that S =>n-1 z because ________
z is in BP because ________
(9) for reason C
(6) for reason A
(2) for reason B
(7) for reason A
