Context Free

Question 1

• Given L, build the grammar G. Then prove that L=L(G) by mutual induction.
  • Exams: 19-01-22, 21-09-03,
  • PDF: 2.1

Answer 1

…

Question 2

• Given L, tell if its context-free (pumping).
  
  • Exams: 19-03-13, 20-01-27, 21-01-25, 21-06-28,
  • PDF: 2.2, (2.3?), 2.4, 2.5, 2.6,
  • Slide: 7.2.16

Answer 2

…

Question 3

• Given generic L1 and L2, tell if intersection/concatenation/… is regular/context free.
  
  • Exams: 19-03-13, 20-01-27,
  • PDF: 2.7,
  • Slide: 7.2.42

Answer 3

…

Question 4

• Given grammar G, remove e-prod, reduce to chomsky
  
  • Exams: 19-09-13, 20-02-17
  • Slide: 7.1.40

Answer 4

…

Question 5

• Algorithm to verify if string is in language (also specify the algorithm)
  
  • Exams: 19-06-28, 21-06-28,

Answer 5

…

Question 6

• Is CFL closed to the operator P(L)={…}?:
  
  • PDF: 2.8

Answer 6

…

Question 7

• Theory:
  
  • Tell why CFL is not open to the complement operation. The complement of a CFL is always recursive? (19-09-13,
  • Show that the class of context-free languages is not closed under intersection. Specify in detail the construction that takes as input a PDA P and a DFA A and produces a PDA P’ that accepts the language L(P)∩ L(A). (21-02-12,

Answer 7

…