CS 4384 — Automata Theory, Homework 5

Download PDF

Let be an alphabet, a CFL and, a string. Prove that the language

is a CFL.

This language is regular, thus it is a CFL. To show it is regular, let us create a DFA for this language.

Observe that the word in the definition of the language cannot contain the character “1”. This means that the string can be described by the regular expression 1*0*, with the corresponding DFA:

Prove that the following language is not context-free.

Let Let Let such that and Let Then then there are several cases:

Thus this language is not context-free by the pumping lemma for CFLs.

Prove that the following language is not context-free without applying the pumping lemma.

This applies because of the closure of CFLs under intersection with regular languages. Take the regular language . , which is not context-free. Thus, is not context free.

Show that if is a CFG in Chomsky normal form, then for any string of length , exactly steps are required for any derivation of

For every internal vertex (nonterminal) in the derivation tree, there are exactly 2 children, and every leaf (terminal) in the tree, there are exactly 0 children. This is a full binary tree. Because the string has characters, there must be exactly terminals in the derivation tree. Based on this, we would like to count the number of internal nodes in the tree. In a full binary tree, there are vertices. Solving for , we get steps in the derivation tree.