Homework 5
Last updated: Fri, 26 Feb 2021 18:40:28 -0500
Out: Mon March 1, 00:00 EST Due: Sun March 7, 23:59 EST
This is the first homework for material from chapter 2 of the Textbook. Homework Problems
1. String Derivations (4 + 4 = 8 pts)
2. CFGs (4 pts)
3. Pushdown Automata (6 pts)
4. Closure under Context-Free Languages (2 + 2 + 2 = 6 pts) 5. If Regular, Then Context-free (6 pts)
6. README (2 pts) Total: 32 points
Submitting
Submit this assignment at Gradescope hw5.
The submission should include only pdf or plain text files.
Be sure to assign each page to the correct problem in Gradescope.
Also, don’t forget to submit a README file containing the required information.
1 String Derivations
Here’s a CFG representing a simple Java-like object-oriented language:
⟨CLASS⟩→class ⟨CLSID⟩ extends ⟨CLSID⟩ {⟨FLDDECLS⟩⟨CONS⟩⟨METHS⟩} ⟨F LDDECLS⟩→⟨F LDDECL⟩ ⟨F LDDECLS⟩ ∣ ε
⟨F LDDECL⟩→⟨CLSID⟩ ⟨F LDID⟩ ; ⟨CONS⟩→⟨CLSID⟩(⟨ARGS⟩){super(⟨EXPRS⟩);⟨FLDASSIGNS⟩}
⟨FLDASSIGNS⟩→⟨FLDASSIGN⟩⟨FLDASSIGNS⟩ ∣ ε ⟨FLDASSIGN⟩→this.⟨FLDID⟩=⟨EXPR⟩;
⟨METHS⟩→⟨METH⟩⟨METHS⟩ ∣ ε ⟨METH⟩→⟨CLSID⟩⟨METHID⟩(⟨ARGS⟩){return ⟨EXPR⟩;}
⟨ARGS⟩→⟨ARGS+⟩ ∣ ⟨ARG⟩ ∣ ε ⟨ARGS+⟩→⟨ARG⟩ , ⟨ARGS+⟩ ∣ ⟨ARG⟩
⟨ARG⟩→⟨CLSID⟩ ⟨ARGID⟩
⟨CLSID⟩→ class names can be any string in [a-zA-Z]+
⟨METHID⟩→ method names can be any string in [a-zA-Z]+ ⟨FLDID⟩→ field names can be any string [a-zA-Z]+ ⟨ARGID⟩→ arg names can can be any string in [a-zA-Z]+
⟨EXP RS⟩→⟨EXP RS+⟩ ∣ ⟨EXP R⟩ ∣ ε
⟨EXP RS+⟩→⟨EXP R⟩ , ⟨EXP RS+⟩ ∣ ⟨EXP R⟩
⟨EXPR⟩→⟨V AR⟩ ∣ ⟨EXPR⟩.⟨FLDID⟩ ∣ ⟨EXPR⟩.⟨METHID⟩(⟨EXPRS⟩) ∣ new ⟨CLSID⟩ (⟨EXP RS⟩) ∣ (⟨CLSID⟩) ⟨EXP R⟩
⟨V AR⟩→ variable names can be any string in [a-zA-Z]+
(Yes, real-world languages are much more complicated than textbook examples.)
The terminals of this grammar are the tokens, i.e., the “words”, of the language, which includes keywords (like class), identifiers (like class or field names), parens, braces, and punctuation (like dot, semicolon, or comma).
NOTE: this means all names (e.g., class names, variable names, etc.) should be leaves in a parse tree. You don’t need to separate them into individual characters.
Whitespace is not included in the terminals and should be ignored. Give a parse tree or derivation for the following strings (i.e., programs): 1. class A extends Object { A() { super(); } }
2. class Pair extends Object {
Object fst;
Object snd;
Pair(Object fst, Object snd) {
super(); this.fst=fst; this.snd=snd;
}
Pair setfst(Object newfst) {
return new Pair(newfst, this.snd);
} }
2 CFGs
Create a CFG that generates the following language L.
You can assume alphabet Σ = {0, 1}.
L = {w ∣ w = FLIP(w)}, where FLIP is from The FLIP Operation in Homework 4.
3 Pushdown Automata
Create a pushdown automata that recognizes language L from the previous problem. You can either draw a diagram or give a formal description.
4 Closure under Context-Free Languages
Show that the following operations are closed under context-free languages: union
concatentation Kleene star
5 If Regular, Then Context-free
Give a proof by induction on regular expressions that:
For any language A, if A is regular, then A is also context-free.
You may assume that the statements from the previous Closure under Context-Free Languages problem are proved.