Copyright © 2007 Gradiance Corporation.
Gradiance Online Accelerated Learning
CFG's
1.
Consider the grammars:
G1: S → SaS | a G2: S → SS | ε G3: S → SS | a G4: S → SS | aa G5: S → Sa | a G6: S → aSa | aa | a G7: S → SAS | ε
Describe the language of each of these grammars. Then, identify from the list below a pair of grammars that define the same language.
a)
G1, G2
b)
G6, G2
c)
G1, G6
d)
G3, G7
2.
Programming languages are often described using an extended form of context-free grammar, where square brackets are used to denote an optional construct. For example, A → B[C]D says that an A can be replaced by a B and a D, with an optional C 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 productions:
A → B[CD]EF | BC[DE]F
Convert this pair of extended productions to conventional productions. Identify, from the list below, the conventional productions that are equivalent to the extended productions above.
A → BA1F
A1 → CD | DE
A → BCDEF | BEF
A → BA1EF | BCA2F
A1 → CD
A2 → DE
A1 → CD | ε
A2 → DE | ε
3.
Consider the languge L={a}. Which grammar defines L?
G1:S → AB|a, A → b
G1:S → AB|C, A → b, C → ε
G1:S → AC|C, A → b
G1:S → AC|a|ab, A → c|ε
4.
The grammar G:
S → SS | a | b
is ambiguous. That means at least some of the strings in its language have more than one leftmost derivation. However, it may be that some strings in the language have only one derivation. Identify from the list below a string that has exactly TWO leftmost derivations in G.
b
abab
abbab
aba
5.
Here is a context-free grammar G:
S → AB
A → 0A1 | 2
B → 1B | 3A
Which of the following strings is in L(G)?
0211300021
021300211
00213021
0021113002111
