Proofs and Programming

$1.$ Consider the language of all strings over S $=\{$a$,$ b$\}$ that contain exactly twice as many

occurrences of a as occurrences of b$.$ The strings $$aab$$aba$$ aabbaa$$ would all be in this

language, but strings like $$aaa$$abbba$$ and $$bbbaa$$ would not. Use the pumping lemma for

regular languages to prove that this language is not regular.

For this problem, provide an electronic text version of your solution.

$2.$ Is the class of context$-$free languages at least as large as the class of regular languages? To

prove this show that any NFA has an equivalent CFG by writing a program called

nfa$\_$to$\_$cfg$.$cpp$.$

This program will read an NFA description from a file. The NFA will be given in the same

format as in project $1.$ The NFA will have no more than $6$ states and no more than $20$

transitions. The alphabet for the NFA is $\backslash$Sigma $=\{$a$,$ b$,$ c$\}.$ You will output an equivalent CFG to

standard out by listing its rules. The CFG production rules must be stored internally in an

ADT of your choice. Do this carefully so the production rules could be easily parsed. The

CFG should use variables with names like V$0,$ V$1,...,$ Vn $($that way you can have as many

variables as you like$).$ V$0$ will always be assumed to be the start variable. The CFG need not

be in Chomsky normal form. You will output the CFG using a format like the following:

V$0->$ V$1$

V$1->$ a V$1$

V$1->$

V$2->$ b V$2$

V$2->$

The string on the right of each rule will be space$-$delimited. The $->$ is also space delimited.

Rules that have epsilon on the right will simply have empty definitions.

As an example, the NFA given as:

trans $0$ a $0$

trans $0$ b $0$

trans $0$ c $0$

trans $0$ a $1$

trans $1$ b $2$

trans $2$ c $3$

trans $0$ b $4$

trans $4$ b $5$

trans $5$ b $3$

trans $3$ a $3$

trans $3$ b $3$

final $3$

could produce the CFG $($this depends on how you handle the start state transitions and how

you choose to number your states$)$:

V$0->$ a V$0$

V$0->$ b V$0$

V$0->$ c V$0$

V$0->$ a V$1$

V$1->$ b V$2$

V$2->$ c V$3$

V$0->$ b V$4$

V$4->$ b V$5$

V$5->$ b V$3$

V$3->$ a V$3$

V$3->$ b V$3$

V$3->$

So$,$ this process is pretty easy. Why? The language accepted by an NFA is regular. A CFG

for a regular language is straightforward because it must only capture iteration and does not

need to capture recursive structures in the language. Begin to think about how you would

convert the above CFG to Chomsky normal form.

$3.$ Is the class of context$-$free languages strictly larger than the class of regular languages?

How can this be shown? Find a known non$-$regular language and show that it is context free.

How about the language from the first problem above? Show that this language is context

free. You have two choices here; either construct a CFG that describes the language in

problem $1$ or construct a PDA that accepts the language in problem $1.$ Since this language

could not be pumped using the Pumping Lemma for Regular Langauages, as shown in

problem $1,$ we complete the proof.

For this problem, provide an electronic text version of your solution or a JFLAP file.