Description
0. [4 points] Give a PDA for the following language over ∑ = { (, ), [, ], a, # } with end-mark “#”:
L0 = { w# | w is a string over { (, ), [, ], a } consisting of lists of zero or more a’s between balanced
parentheses of two types }
E.g., L0 contains: #, ()#, (a)#, [ a a ]#, []( a )#, ([ a ])()#, [([ a a a ])]#, etc.
E.g., L0 does not contain: ε, a#, #(), (]#, ()a#, ((a)#, [ # ]#, []( ( ) a )#, ( a ])()#, [[ a a a ])]#, etc.
Scoring: 3 points for correct PDA + 1 point if your PDA is deterministic.
1. Consider the following CFG G = (V, ∑, R, P), where:
V = { P, Type, Pl, Pl1, Body, St, Else }
∑ = { main , ( , ) , int , char , void , { , } , ; , , , = , if , exp , else , id }
R = { P – > Type main ( Pl ) { Body }
Type – > int | char | void
Pl – > ε | id Pl1
Pl1 – > , id Pl1 | ε
Body – > St ; Body | St ;
St – > id = exp
St – > if ( exp ) St Else | if ( exp ) { Body } Else
Else – > else St | else { Body } | ε
}
This grammar describes a very small portion of the syntax of a programming language similar to the C
programming language.
1.a. [1 points] Show a derivation tree in G for the string:
void main () { if (exp) id = exp ; if (exp) id = exp else id = exp ; }
1.b. [1 points] Show a left-most reduction in G for the same string, and underline the handle at each step
as shown in class.
Some groups of production rules describe particular language features. E.g., the rule:
“ P – > Type main ( Pl ) { Body } ”
describes the overall structure of programs. The rules for variables Pl and Pl1 describe parameter lists.
The rules for variables St and Else describe the assignment statement and if statements. Some of these
language features could be represented using only a DFA or equivalent model; while some features
can only be described correctly using the Context Free Grammar (CFG) model.
1.c. [2 points] Identify the language feature(s) which require the CFG model and very briefly explain why
they require a CFG to define them.
2. [4 points] Consider the following language over ∑ = { 0, 1 }:
L2 = { 0
r
1 0s
1 0t
| r, s, t ≥ 0 and r < s > t }
Prove that L2 is not context free using the Pumping Lemma for context free languages.
eof