Models - Context-Free Grammar

Question 1

Informally, what elements define a context-free grammar (CFG)?

Answer 1

Question 2

Define a CFG

Answer 2

Question 3

Define a context-free language (CFL)

Answer 3

Question 4

What is the relationship between Regular languages and CFLs?

Answer 4

Question 5

Answer 5

~ Every word of at least "kavua hanipuach" size has a structure that can be inflated with any i.

Question 6

How can we prove that a language is not context-free?

Answer 6

Question 7

Let L1 and L2 be two CFLs. is L1∩L2 a CFL?

Answer 7

Question 8

Answer 8

Question 9

Answer 9

Question 10

What is CFL closed to? What is it not closed to?

Answer 10

CFL is closed to Union, concatenation and Kleen star.

CFL is not closed to intersection and complement.

Question 11

Please give examples of languages in CFL.

Answer 11

Also wwrev is in CFL

Question 12

Please give examples of languages not in CFL.

Answer 12

Question 13

How would you go about solving this question?

Answer 13

First write out the first few word in the language. Then the grammar will (hopefully) come to you.

Question 14

Answer 14

Notes:
1. Always try working with languages like Sigma-star
2. when listing the languages in CFL - don’t just write “REG” - list them!