CH 3 - Context-free Languages and Pushdown Automata

Question 1

Define a PDA.

Answer 1

Question 2

Define a configuration of P.

When does a PDA accept an input word?

Answer 2

Question 3

State and prove a theorem (part a and b) on which languages a PDA recognises.

Answer 3

Question 4

Define a context free grammar (CFG).

How do you make a word of a language L(A), where A is a variable?

Define a derivation.

Answer 4

Question 5

When is a language context-free?

Define a parse tree for a derivation.

Answer 5

Question 6

Define Chomsky normal form.

We will show how you can convert any CFG to one in Chomsky normal form.

(1) Describe the bad epsilon-rule process.

State a lemma on a CFG that start cleanly.

Answer 6

Question 7

(2) Describe the unit rule process.

State a lemma on a CFG that starts cleanly and has no bad epsilon-rules.

State a theorem on the existence of a Chomsky normal form language.

Answer 7

For a CFG, G, there exists a CFG G_1 in Chomsky
Normal Form such that L(G) = L(G1).

Question 8

Answer 8

Question 9

State the theorem on context-free languages and PDAs.

Give a method for constructing a PDA that accepts the language generated by a CFG.

State a corollary on the classes of regular and context-free languages.

Practice with Example 3.4.2. and Example 3.4.3.

Answer 9

Corollary 3.4.4. The class of regular languages is a proper subset of the class of context-free languages.

Question 10

Give two methods for showing a language is context-free.

Showing a language is not context-free: State the Pumping Lemma for context-free languages.

Practice using the Pumping Lemma for a contradiction in Example 3.5.2. and Example 3.5.3.

Answer 10