Copyright © 2007 Gradiance Corporation.
Gradiance Online Accelerated Learning
CFG's --- Additional Questions
1.
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 _______.
For which of the steps above the appropriate reason is contained in the following argument: "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."
a)
6a
b)
5b
c)
5a
d)
1
2.
Identify in the list below a sentence of length 6 that is generated by the grammar S → (S)S | ε
( ) ( ) ( )
) ) ) ( ( (
) ) ( ( ) (
) ( ( ) ( )
3.
Programming languages are often described using an extended form of context-free grammar, where curly brackets are used to denote a construct that can repeat 0, 1, 2, or any number of times. For example, A → B{C}D says that an A can be replaced by a B and a D, with any number of C's (including 0) between them. This notation does not allow us to describe anything but context-free languages, since an extended production can always be replaced by several conventional productions.
Suppose a grammar has the extended production:
A → a{b}B
Convert this extended production to conventional productions. Identify, from the list below, the conventional productions that are equivalent to the extended production above.
A → aA1B
A1 → A1b | ε
A1 → bA1 | b
A1 → b | ε
A1 → A1b | b
4.
Consider the grammar G and the language L:
G: S → AB | a | abC, A → b, C → abC | c
L: {w | w a string of a's, b's, and c's with an equal number of a's and b's}
Grammar G does not define language L. To prove, we use a string that either is produced by G and not contained in L or is contained in L but is not produced by G. Which string can be used to prove it?
aabb
aba
ababc
abababc
5.
For which of the steps above the appropriate reason is contained in the following argument: "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."
6b
6.
Consider the following languages and grammars.
G1: S → aA|aS, A → ab G2: S → abS|aA, A → a G3: S → Sa|AB, A → aA|a, B → b G4: S → aS|b
L1: {aib| i=1,2,...} L2: {(ab)iaa| i=0,1,...} L3: {aib| i=2,3,...} L4: {aibaj| i=1,2,..., j=0,1,...} L5: {aib| i=0,1,...}
Match each grammar with the language it defines. Then, identify a correct match from the list below.
G3 defines L3.
G4 defines L3.
G2 defines L2.
G3 defines L5.
7.
Consider the grammar G1: S → ε, S → aS, S → aSbS and the language L that contains exactly those strings of a's and b's such that every prefix has at least as many a's as b's. We want to prove the claim: G1 generates all strings in L.
We take the following inductive hypothesis to prove the claim:
For n < k, G1 generates every string of length n in L.
To prove the inductive step we argue as follows:
"For each string w in L either ____________(a1) or ______________(a2) holds. In both cases we use the inductive hypothesis and one of the rules to show that string w can be generated by the grammar. In the first case we use rule S → aS and in the second case we use rule S → aSbS."
Which phrases can replace the ____________ so that this argument is correct?
a1: each prefix has equal number of a's and b's. a2: there is a b in string w such that the part of the string until the b belongs in L by inductive hypothesis and the part after this b belongs in L by inductive hypothesis.
a1: w can be written as w=aw'bw'' where for both w' and w'' it holds that each prefix has as many a's as b's. a2: each prefix has more a's than b's.
a1: each prefix has more a's than b's. a2: there is a unique b in string w such that for the part of the string until the b (b also included) each prefix has as many a's as b's and for the part after b each prefix has as many a's as b's.
a1: w can be written as w=aw' where for each prefix of w' has as many a's as b's. a2: there is a b in string w such that the part of the string until the b (b also included) has all prefixes with as many a's as b's and the part after this b has all prefixes with as many a's as b's.
8.
Here are eight simple grammars, each of which generates an infinite language of strings. These strings tend to look like alternating a's and b's, although there are some exceptions, and not all grammars generate all such strings.
The initial symbol is S in all cases. Determine the language of each of these grammars. Then, find, in the list below, the pair of grammars that define the same language.
G1: S → aB, B → bS, B → b
G2: S → aB, B → bS, S → a
G1: S → abS, S → ab
G2: S → aB, B → bS, S → ab
G2: S → aB, B → bS, B → ab
G1: S → aB, B → bS, B → ab
9.
Which of the following grammars derives a subset of the language:
{x | x contains a and c in proportion 4:3 and there are no two consecutive c's}?
S → acacaca S → SaScSaScSaScSaS S → SaSaSaScSaScSa
S → acacaca S → SacSaScSaScSaS
S → acacaca S → SaSaSaScSaScSaS
S → ε S → aacacac S → SaScSaScSaScSa
10.
Consider the grammar G with start symbol S:
S → bS | aA | b A → bA | aB B → bB | aS | a
Which of the following is a word in L(G)?
babbbabaaaa
ababbbbbb
bababaababaa
babbbaaaaaba
11.
Consider the grammars:
G1: S → AB, A → aAA|ε , B → abBB|ε G2:S → CB, C → aCC|aC|a, B → abBB|abB|ab G3:S → CB|C|B| ε , C → aCC|aC|a, B → abBB|abB|ab G4:S → ASB|ε, A → aA|ε, B → abB|ε G5:S → ASB|AB, A → aA|a, B → abB|ab G6:S → ASB|aab, A → aA|a, B → abB|ab
Describe the language of each of these grammars. Then, identify from the list below a pair of grammars that define the same language?
G3 and G4
G3 and G6
G2 and G6
G1 and G2
12.
Which of the following grammars derives a subset Ls of the language: L= {x | (i) x contains a and c in proportion 4:3, (ii) x does not begin with c and (iii) there are no two consecutive c's} such that Ls is missing at most a finite number of strings from L.
S → acacaca, S → SaSaSaScSaScSaS
S → ε , S → SaScSaScaSaSaSaS
S → ε, S → SaScSaScSaScSaS, S → A, A → acaca
S → ε , S → SaScSaScSaSaSaS
13.
Consider the grammar G1:
S → ε | aS | aSbS
Which of the following is correct (for a choice to be correct, all propositions must be correct)?
Grammar G1 generates the string aab in two different ways -- different parse trees.
a) G1 generates all and only the strings of a's and b's such that every prefix has at least as many a's as b's. b) The inductive hypothesis to prove it is: For n < k, it holds that: For any word in G1, any prefix of length n, is such that all its prefixes contain at least as many a's as b's.
a) G1 generates all and only the strings of a's and b's such that every prefix has at least as many a's as b's. b) The following inductive hypothesis will prove it: For n < k, it holds that: Any word in G1 of length n, is such that all its prefixes contain at least as many a's as b's.
The string aaba is not generated by the grammar.
14.
Which of the following pairs of grammars define the same language?
G1: S → AB, A → aAA|ε , B → baBB|ε G2: S → CB|B|ε , C → aCC|aC|a, B → baBB|baB|ba
G1: S → SaScSa|aca|ε G2: S → SaSAaS|aca, A → cS|ε
G1: S → AB, A → aAA| ε, B → bBB|ε G2: S → AB|A|B|ε , A → aAA|aA|a, B → bBB|bB|b
G1: S → SaScSaS|aca|ε G2: S → SaBaS|aca, B → cS|ε
