CSE 105 Theory of Computation - Home | Computer Science

CSE 105

THEORY OF COMPUTATION

Fall 2016

Today's learning goals Sipser Ch 1.1?1.4

?Are there non-regular languages? ?Pumping Lemma for Regular Languages ?Identify some nonregular sets

DFAs and Counting

Which of the following languages is regular?

? L1 = {0n1n | n < 10} ? L2 = {0n1n | n > 10}

A) L1 B) L2 C) Both L1 and L2 D) Neither L1 nor L2 E) I don't know

DFAs and Counting

Which of the following languages is regular?

? L1 = {0n1n | n < 10} ? L2 = {0n1n | n > 10}

Correct answer is (A): Only L1

Why is L1 regular?

? Easy: because it is a finite language (of size 10)

But why is L2 not regular? Definitions look so similar!

A DFA for L1

Give a DFA for

? L1 = {0n1n | n < 10}

How many states do you need?

A) 10 (or fewer) B) 20 (or fewer) C) 100 (or fewer) D) Exaclty 2048 E) I don't know

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download