Reference no: EM132496642

ECS421U Automata and Formal Languages - Queen Mary University

Problem 1: CFGs, PDAs, parsing
(a) Give a context-free grammar G accepting the same language as the regular expression:
1(0 + 1)(0 + 1)^∗
(b) Consider the following context-free grammar G over Σ = {0, 1, 2}, with start variable S:
S → 1Y | 2S | ε
Y → S1 | 0Y10 | 0
(i) Using the rules of G, construct parse trees for the words 2, 210 and 210010.
(ii) Explain why the grammar is not in Chomsky normal form (CNF). One reason is sufficient.
(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.
(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.
(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.
(ii) For each word of yours from part (i) that is in the language give an accepting derivation.
(iii) Describe in English the language accepted by G, or give a formal definition of it.
(iv) Give a PDA A recognising the same language as G.
(v) For two of the accepted words from part (i), give accepting runs of your PDA.

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 Problem 1(c).

Problem 2: Java Implementation

Use the provided files Question2.java, CFG.java and Rule.java for the following exercises.
• You should write your code in Question2.java, by altering only the TODO parts of the file. In particular, keep the body of main intact.
• You should not change CFG.java and Rule.java.
In Question2.java 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 Question2.java respectively. In your report, include the code you wrote for each of these methods.
(i) The initial CFG of Problem 1(b).
(ii) Taking Σ = { ( , ) } (i.e. the alphabet contains left brackets and right brackets):
S → ε | (S) | SS
(iii) Taking Σ = {0, 1, 2, 3}, and start variable S:
S → 3X | 1X
X → 3S | 1Y | ε
Y → 0X | 3X | ε
(b) Implement in Question2.java the method:
public static void runThem()

which generates the CFG of Problem 1(b) (which is already implemented in Question2.java) 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.
(c) We saw that a CFG is in Chomsky-Normal Form (CNF) if its rules satisfy some specified criteria. Implement in Question2.java 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
false
• G.checkLetter("2") returns true, while G.checkLetter("S") and G.checkLetter("12") return false.

Attachment:- Automata and Formal Languages.rar