2 Parse This question concerns the following Chomsky normal form CFG with = {a,b}: S...

Transcribed Image Text:

2 Parse This question concerns the following Chomsky normal form CFG with Σ = {a,b}: S→ AV | BX | b M→ AV | BX | b V→ MA X→ BX | b B → b Part A (3pts). What is the language of this grammar? Extra credit (2pts). Give an equivalent CFG with only 4 rules. Part B (8pts). Let t = abba] Recall that M[E. s] in CYK lists the variables that derive u,...+-1- 1. Which variable(s) if any are listed in the M[1,1] cell of the table of CYK subproblems? 2. Which variable(s) if any are listed in the M[2.1] cell of the table of CYK subproblems? 3. Which variable(s) if any are listed in the M[2, 3] cell of the table of CYK subproblems? 4. Which cell in the table of CYK subproblems tells whether abba is in the language of this grammar, and what must that cell contain to conclude that the string is in the language? Part C (4pts). Draw a parse tree for the string = abba under this grammar. 2 Parse This question concerns the following Chomsky normal form CFG with Σ = {a,b}: S→ AV | BX | b M→ AV | BX | b V→ MA X→ BX | b B → b Part A (3pts). What is the language of this grammar? Extra credit (2pts). Give an equivalent CFG with only 4 rules. Part B (8pts). Let t = abba] Recall that M[E. s] in CYK lists the variables that derive u,...+-1- 1. Which variable(s) if any are listed in the M[1,1] cell of the table of CYK subproblems? 2. Which variable(s) if any are listed in the M[2.1] cell of the table of CYK subproblems? 3. Which variable(s) if any are listed in the M[2, 3] cell of the table of CYK subproblems? 4. Which cell in the table of CYK subproblems tells whether abba is in the language of this grammar, and what must that cell contain to conclude that the string is in the language? Part C (4pts). Draw a parse tree for the string = abba under this grammar.

Answer rating: 100% (QA)

Part A The language of this grammar is anbn n 0 An equivalent CFG with only 4 rules is S a... View the full answer