Copyright © 2006 Gradiance Corporation.

 

 

     

Context-Free Grammars

 

 

 

Grammars, ambiguity, extended grammars.

 

1.  

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 → BC{DE}F
 

Convert this extended production to conventional productions. Identify, from the list below, the conventional productions that are equivalent to the extended production above.

 

 

 

 a)  

A → BCA1F
A1 → DE | ε

 

 b)  

A → BCA1F
A1 → A1DE | DE

 

 c)  

A → BCDEA1F
A1 → DEA1 | ε

 

 d)  

A → BCA1F
A1 → DEA1 | ε

 

 

 

 

 

2.  

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)?

 

 

 

 a) 

ababbbbbbbb

 

 b) 

ababba

 

 c) 

ababbbbb

 

 d) 

ababbbbbbbbb

 

 

 

 

 

3.  

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 → BC[DEFG]HI | BCDE[FGH]I
 

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)  

A → BCA1HI | BCDEA2I
A1 → DEFG | ε
A2 → FGH | ε

 

 b)  

A → BCDEFGHI | BCHI | BCDEI | BCI

 

 c)  

A → BCA1HI | BCDEA2I
A1 → DEFG
A2 → FGH

 

 d)  

A → BCA1I
A1 → DEFG | FGH

 

 

 

 

 

4.  

Consider the following four grammars:

  1. S → abS | ab
  2. S → SS | ab
  3. S → aB; B → bS | b
  4. S → aB | ab; B → bS

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.

 

 

 

 a) 

G1: S → aB, B → bS, B → b    G2: S → aB, B → bS, S → ab

 

 b) 

G1: S → aB, B → bS, B → b    G2: S → aB, B → bS, S → a

 

 c) 

G1: S → aB, B → bS, B → a    G2: S → aB, B → bS, B → b

 

 d) 

G1: S → aB, B → bS, B → ab    G2: S → SS, S → ab

 

 

 

 

 

5.  

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.

 

 

 

 a) 

aaaa

 

 b) 

abab

 

 c) 

abbab

 

 d) 

aab

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6.  

Here is a context-free grammar G: 

S → AB
A → 0A1 | 2
B → 1B | 3A

Which of the following strings is in L(G)?

 

 

 

 a) 

002111300211

 

 b) 

00213021

 

 c) 

00021132

 

 d) 

00211100211