Week 2 - CFG versus FA

Question 1

TRUE OR FALSE: A DFA can be converted into a CFG.

Answer 1

TRUE, any DFA has an equivalent CFG.

Question 2

How do you convert a DFA to a CFG.

Answer 2

Give every state a variable name. Each state rule has a rule for each forward transition it has. The left hand side of the rule is the state variable name, and the right hand side is the transition label concatentated onto the variable name of the state it transitions to. Once you have all these rules, add one more rule which substitutes the final state variable for an ε.

Question 3

TRUE OR FALSE: A regular language is a context-free language.

Answer 3

TRUE, because you can convert a DFA to a CFG.

Question 4

TRUE OR FALSE: There are context-free languages that are not regular.

Answer 4

TRUE.