Java代写 | ECS421U Coursework 2 – CFG and PDA Algorithms


ECS421U Coursework 2 – CFG and PDA Algorithms
Deadline: 31 March 2020, 10am. Submit on QM+.
Weight: 10% of module mark.
Content: Context-Free Grammars, Parsing, Pushdown Automata, Code implementing Grammars.
Who: This coursework is an individual marked assignment. You must not get help from
other students, compare their solutions to yours, or show you solutions to others.
What to submit: You must submit two files:
1. A pdf file, named report.pdf. This should contain your solutions to the parts of
Questions 1 and 2 that you attempted. For the parts of Question 2 that require coding,
include in the report a transcript of the code you filled in and (where needed) a snapshot
of the printout.
2. A java file, named This should include in full your code for Question 2.
Before you begin, read through the whole description of the coursework to make sure that you know
what is required of you. Note that in the last page we have included a short Appendix to help you
with the Java coding parts.
Report Writing
Ensure that your report is clearly structured and any formal notation required follows the guidelines
provided in the previous weeks. Moreover:
• Write clearly, and take care of grammar errors and typos.
• Use proper formatting of the various sections. Include your ID or name on your report.
• If scanned images are used, make sure they are clear and readable in A4 size.
• Where requested, make sure you include code transcripts and snapshots of printouts.
Though hand-written (scanned) reports will be accepted, it is best to prepare your report electronically
and either draw your automata using a drawing tool, or hand-draw them and embed them in the
report as (clear) pictures.
[8 marks]
You will first work with CFGs and PDAs as was done in previous labs and exercises. The second part
of this coursework will then require some implementations in Java.
Question 1: CFGs, PDAs, parsing
(a) Give a context-free grammar G accepting the same language as the regular expression:
1(0 + 1)(0 + 1)∗
[3 marks]
(b) Consider the following context-free grammar G over Σ = {0, 1, 2}, with start variable S:
S → 1Y | 2S | ε
Y → S1 | 0Y 10 | 0
(i) Using the rules of G, construct parse trees for the words 2, 210 and 210010. [6 marks]
(ii) Explain why the grammar is not in Chomsky normal form (CNF). One reason is sufficient.
[2 marks]
(iii) Using any of the techniques we have seen in the lectures, construct a CNF grammar
accepting the same language as G.
Make sure you include in your answer all individual steps you followed. [12 marks]
(iv) Using the rules of your CNF grammar and the CYK algorithm, verify whether the following
words are in the language of G: 121, 122. [10 marks]
(c) Consider the following context-free grammar G over Σ = {0, 1, 2, 3}, with start variable S:
S → 1S1 | 3S3 | Y
Y → 20 | 20Y
(i) Give three example words in the language of the grammar G, and three words (from Σ

not in it. Make sure that your accepted words combined use all of the alphabet letters.
[3 marks]
(ii) For each word of yours from part (i) that is in the language give an accepting derivation.
[3 marks]
(iii) Describe in English the language accepted by G, or give a formal definition of it.
[3 marks]
(iv) Give a PDA A recognising the same language as G. [10 marks]
(v) For two of the accepted words from part (i), give accepting runs of your PDA. [6 marks]
In the rest of this coursework you will work with a Java implementation of Context-Free Grammars.
The implementation of CFGs will use the classes CFG and Rule, similar to the classes FSA and
Transition that you worked with in the previous coursework:
public class CFG {
public String alphabet[];
public String vars[];
public Rule rules[];
public String startVar;
public CFG(String[] a, String[] v, Rule[] r, String sv) {
alphabet=a; vars=v; rules=r; startVar=sv;
// … plus public and private methods
So, objects of the class CFG can be seen as tuples containing four elements. If G is an instance of the
class CFG, representing the CFG G = (Σ, V, R, S), we have:
• G.alphabet is an array of strings representing the elements of the alphabet Σ. For example,
if Σ = {a, b} then G.alphabet should be the array {“a”, “b”}.
Note that the array {“a”, “b”} is created by the command: new String[]{“a”, “b”}.
• G.vars is an array of strings representing the variables of G, i.e. the elements of V . E.g. if
V = {S, Y } then G.vars should be the array {“S”, “V”}.
• G.startVar is a string corresponding to the starting variable. In our example, the starting
variable is S, so G.startVar should be “S”.
• G.rules is the set of grammar rules, represented as an array. Grammar rules have their own
Rule class:
public class Rule {
public String var;
public String rhs[];
public Rule(String v, String[] r) {
var=v; rhs=r;
So, a Rule instance r simply contains two fields:
– r.var is the variable on the LHS of the rule
– r.rhs is the RHS of the rule, which is an array of strings (i.e variables and letters).
E.g. to create a new rule S → 1S1 we use: new Rule(“S”,new String[]{“1″,”S”,”1″}).
Returning to G.rules, we can construct e.g. R = {S → ε, S → 0XX, X → 10} using:
new Rule[]{
new Rule{“S”, new String[]{}},
new Rule{“S”, new String[]{“0″,”X”,”X”}},
new Rule{“X”, new String[]{“1″,”0”}} };
Note that when the rule RHS is just ε, it is represented as an empty array (but not null!).
String[] alphabet = new String[]{ “0”, “1”, “2”, “3” };
String[] vars = new String[]{ “S”, “Y” };
Rule[] R = new Rule[] {
new Rule(“S”, new String[]{“1″,”S”,”1″}),
new Rule(“S”, new String[]{“3″,”S”,”3″}),
new Rule(“S”, new String[]{“Y”}),
new Rule(“Y”, new String[]{“2″,”0”})
new Rule(“Y”, new String[]{“2″,”0″,”Y”})
new CFG(alphabet,vars,R,”S”);
Figure 1: An implementation of the CFG of Question 1(c).
Question 2: Java Implementation
Use the provided files, and for the following exercises.
• You should write your code in, by altering only the TODO parts of the file.
In particular, keep the body of main intact.
• You should not change and
In there is some DEMO code to help you with what you need to do in this Question!
(a) Write down code implementing each of the CFGs of parts (i), (ii) and (iii) below, in the manner
we explained above (i.e. as was done in Figure 1). Include the code in the methods:
public static CFG generateCFG1()
public static CFG generateCFG2()
public static CFG generateCFG3()
of respectively. In your report, include the code you wrote for each of these
(i) The initial CFG of Question 1(b). [6 marks]
(ii) Taking Σ = { ( , ) } (i.e. the alphabet contains left brackets and right brackets):
S → ε | (S) | SS [6 marks]
(iii) Taking Σ = {0, 1, 2, 3}, and start variable S:
S → 3X | 1X
X → 3S | 1Y | ε
Y → 0X | 3X | ε [6 marks]
(b) Implement in the method:
public static void runThem()
which generates the CFG of Question 1(b) (which is already implemented in
and three CFGs that you implemented in part (a) and runs them, one by one, on the inputs
specified below, using the method isAccepted (the method is explained at the end of this
assignment). Your code should test the CFGs on the following inputs and print the results of
the runs, as follows:
G0 accepts: 2020 […], 120201 […], 2021 […]
G1 accepts: epsilon […], 210 […], 210010 […]
G2 accepts: (()) […], ()(()) […], ((())))( […]
G3 accepts: 11011 […], 11010 […], 11001 […]
where the dots should contain yes or no, depending on whether the word is accepted by the
corresponding CFG or not. So, for example, for G2 the words to test are (()), ()(()) and
((())))(. Also, the first word to check for G1 is ε (the empty word). In your report, include:
• The code of your implementation of runThem. • A snapshot of the printout of runThem.
[4 marks]
(c) We saw that a CFG is in Chomsky-Normal Form (CNF) if its rules satisfy some specified criteria.
Implement in a method:
public static Boolean isInCNF(CFG G)
which takes a CFG object G as input and returns true if G represents a CFG that is in CNF,
and false otherwise. In your report, include:
• The code of your implementation of isInCNF, along with a textual explanation of what
it is doing. By explanation, we don’t mean a line-by-line readout of the code but, rather,
an explanation of the idea of your algorithm and the steps followed to implement it.
• A snapshot of the printout of testIsInCNF.
Hint: One solution is to use a for-loop to go over all rules of the grammar and check if they
(all) satisfy the CNF criteria. You can also use the following methods from the class CFG:
public boolean checkVar(String v)
public boolean checkLetter(String s)
which check if the input string is a valid variable or alphabet letter respectively for the given
CFG and return true or false accordingly. For example, if G is the CFG instance constructed
in Figure 1 then:
• G.checkVar(“S”) returns true, while G.checkVar(“W”) and G.checkVar(“2”) return
• G.checkLetter(“2”) returns true, while G.checkLetter(“S”) and G.checkLetter(“12”)
return false.
[(for code and explanation) 12 marks]
Appendix: Helper functions
The file has a couple of implemented helper methods:
• public static void checkPrintCFG(CFG G, String name)
It first checks that the input CFG G is a valid CFG representation, running a series of tests. If
it is not valid, it prints an error message. Otherwise, it prints out G giving it the name name.
So, if we call checkPrintCFG(G, “G42”) we will get a printout starting with G42 = . . . .
• public static Boolean isAccepted(CFG G, String[] w)
It takes an CFG object G and an array of strings w as inputs, and returns true if G accepts w,
and false otherwise. The method uses a naive parsing algorithm and only works if G satisfies
a certain “progress” property, which the grammars in part (a) do satisfy.


本网站支持淘宝 支付宝 微信支付  paypal等等交易。如果不放心可以用淘宝交易!

E-mail: [email protected]  微信:itcsdx