[SOLVED] CS Java Homework 5

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, dont forget to submit a README file containing the required information.
1 String Derivations
Heres a CFG representing a simple Java-like object-oriented language:
CLASSclass CLSID extends CLSID {FLDDECLSCONSMETHS} F LDDECLSF LDDECL F LDDECLS
F LDDECLCLSID F LDID ; CONSCLSID(ARGS){super(EXPRS);FLDASSIGNS}
FLDASSIGNSFLDASSIGNFLDASSIGNS FLDASSIGNthis.FLDID=EXPR;
METHSMETHMETHS METHCLSIDMETHID(ARGS){return EXPR;}

ARGSARGS+ ARG ARGS+ARG , ARGS+ ARG
ARGCLSID 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 RSEXP RS+ EXP R
EXP RS+EXP R , EXP RS+ EXP R
EXPRV 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 dont 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.