June 11th, 2012

# JasTeX → Turing Machine → Simulation

Tuesday. Chapter 17. Computability

Chapter 17: Computability

A good write-up for an explanation of the Church-Turing Thesis.

“The Church-Turing thesis is meant to define the idea of effective calculability. Kurt Godel first described these functions, which he called general recursive. Church then used lambda-definability to describe the functions. Turing wrote that a function is effectively calculable if its values can be found through purely mechanical processes, or those that can be carried out by machines. Turing’s definition turns out to be the equivalent of the other two, but his gives it a mathematically expressible form. This was accomplished with Turing machines. Turing said that if a function’s values are calculable, then the function can be computed with such a machine.” – Matt Martin

NOVA scienceNOW | Twin Prime Conjecture | PBS

The Halting Problem – Part 1

The Halting Problem – Part 2

Wednesday: Chapter 18 Uncomputability

Chapter 18: Uncomputability

Thursday: Chapter 19 Cost Models

Chapter 19: Cost Models

Monday: Chapter 20 Complexity

Tuesday: Chapter 21 Complexity

## CPSC 326. Class 10. Summer 2012

June 10th, 2012

Turing Machines

Chapter 16: Turing Machines

Some excerpts from Turing’s papers:

Videos

HW for Wednesday.
Please read Alan Turing, the Stanford Encyclopedia of Philosophy, http://plato.stanford.edu/entries/turing/.

Using at least 100 words, without using direct quotes, write an explanation or exposition of the Church-Turing thesis. If you’re not sure of what an exposition is, take a look at http://dictionary.reference.com/browse/exposition.

Identify the subject of each of the following images, and write at least three sentences stating the relationship of the person, object, or location represented to the material that appears in the entry “Alan Turing” in the Stanford Encyclopedia of Philosophy.

 image 1 image 2 image 3 image 4 image 5 image 6 image 7 image 8 image 9 image 10 image 11 image 12

Page 233 Ex 1,2 4. For extra 3,5, 6

## CPSC 326. Class 9. Summer 2012

June 5th, 2012

In the last class we covered topics in Chapters 10 and 11,

• introducing the notion of a grammar
• discussing how all regular languages have a grammar
• discussing how each right-liner grammar produces a regular language
• showed that some languages that are produced form a grammar are not regular
• introduced and used the pumping lemma for regular languages

Still need to mention that each finite language is therefore regular.

Chapter 12: Context-Free Languages

Power Point to Accompany Text, Chapter 12

Each regular language is a CFL, because each regular language has a right-liner grammar and each right-linear grammar is a CFG, so the language is a CFL.

Some languages that are not regular are context-free

Context-Free Grammars

Backus-Naur Form (slide 22)

BNF and EBNF: What are they and how do they work?

BNF Web club

We can move to parse trees from BNF.

To recognize and remove ambiguity.

June 3rd, 2012

## Chapter 8 – applications of Regular Expressions

material from previous blog post

Chapter 9 – skip

## Chapter 10 – Grammars

Definition in Section 10.2. A grammar is a four-tuple

The language generated by a grammar. Defined in Section 10.3

Theoretical results:

• each regular language has a grammar
• each Right Linear Grammar generates a regular language
• Note we do not say that every language derived from a grammar is regular

Try exercises in class. Pages 128 – 130. Lots of good ones.

Author’s PowerPoint: Chapter 10: Grammars

## Chapter 11.  NonRegular Languages.

The language {anbn} is not regular

The language {xxR} is not regular

Methods of proof.

Pumping

• pumping lemma. Section 11.3
• pumping-lemma proofs. Section 11.4
• strategies. Section 11.5

Theoretical result

• All finite languages are regular.

Exercises: Any of the ones on page 143.

Author’s powerpoint. Chapter 11: Non-Regular Languages

May 30th, 2012

## Applications of regular expressions

grep searches the named input FILEs (or standard input if no files are named, or the file name – is given) for lines containing a match to the given PATTERN. By default, grep prints the matching lines.

In addition, three variant programs egrep, fgrep and rgrep are available.

• egrep is the same as grep -E.
• fgrep is the same as grep -F.
• rgrep is the same as grep -r.

examples:

grep  inventory.h  *.cpp

ps -ef | grep ernie

But these can be more powerful with regular expressions using:

• * to represent 0 or more repetitions
• |, or, x|y matches wither x or y or both
• () used for grouping
• ^ represents start of line
• \$ represents end of line
• . match any symbol, except \n

regexp cheat sheat

You may alo want to see   ASP/Jscript Email Validation

go to lab and try examples in the text.

egrep ‘a’ names
egrep ‘a.*y’ names
egrep ‘.(..)*’ names
egrep ‘^.(..)*\$’ names
egrep ‘^(0|1(01*0)*1)*\$’ numbers

Use the file /users/ernie/public_html/cpsc326/code/numbers , use cp to copy it to your directory or fetch it using http,  link to numbers, for the file numbers referred to in the text.

Also do exercise 1 page 101.

Regular expressions in Java

use /users/ernie/public_html/cpsc326/code/numbers for numbers

lex

In computer science, lex is a program that generates lexical analyzers (“scanners” or “lexers”). Lex is commonly used with the yacc parser generator. Lex, originally written by Eric Schmidt and Mike Lesk, is the standard lexical analyzer generator on many Unix systems, and a tool exhibiting its behavior is specified as part of the POSIX standard.

Lex reads an input stream specifying the lexical analyzer and outputs source code implementing the lexer in the C programming language.

Structure of a file

definition section
%%

rules section
%%

user subroutines

Examples:

counter.l – counts number of lines and characters in a file

int num_lines = 0, num_chars = 0;
%%

\n       ++num_lines; ++num_chars;
.        ++num_chars;

%%

main() {

yylex();
printf( “# of lines = %d, # of chars = %d\n”,num_lines, num_chars );

}

Produce a c program using
lex counter.l

Produce a run file using
gcc lex.yy.c -o counter -ll

username.l – replaces all occurrence of username with the user’s login name

%%

%%

The examples from the text, pages 98 and 100.

Chapter 8: Regular Expression Applications

Use egrep to find   all numbers divisible by 4 in the file http://paprika.umw.edu/~ernie/cpsc326/numbers

or /users/ernie/public_html/cpsc326/numbers

got to /users/ernie/public_html.cpsc230

Which lines in /users/ernie/public_html/sum.cpp have in-line comments?

Which lines are comments?

Use Java to do the same

## Class 5. Summer 2012.

May 29th, 2012

Chapter 5: Nondeterministic Finite Automata

Do some exercises. Page 54. #2  pg 55 #4,5. Page 57 10

Chapter 6
The subset construction page 65
Convert NFA to DFA. theorem says NFA same as DFA
A language L is L(N) for some NFA N off L is a regular language.

Chapter 6: NFA Applications
Page 71, #3 Page 72 #5

## Chapter 7. Regular Expressions

Formal Definitions
Concatenation of languages
Kleene closure
{a,b}*

A regular expression is a string r that denotes a language L(r) over some alphabet  S. The six kinds of regular expressions and languages…..
Page 76 .. 77

Examples pg 77-78
Regular Expression. —> Regular Language —-> Regular Expression

From another source:

Let Σ be a fixed alphabet.

A regular expression, or regexp for short, is an expression that describes a particular language over Σ.

If r is a regular expression, we write L(r ) for the language described by r .

We may also just use the regexp itself in place of the language it describes.

Primitive (atomic) regular expresions are:

• Φ describes the empty language L(Φ) = Φ;
• ε describes the language L(ε) = {ε } consisting of just the empty string; and
• a for a ε Σ describes the language L(a) = {a} consisting of just the string a of length 1.

Regular expressions can be combined with three possible operators: union, concatenation, and Kleene closure. If r and s are regexps, then so are:

• r+ s describing the language L(r ) U L(s);
• (rs), describing the language L(r )L(s);
• (r*) , describing the language L(r )*

Every regular expression is constructed by these rules; no other regular expressions are possible.

This is an inductive (recursive) definition, since it defined new regular expressions in terms of shorter ones (subexpressions).

Conventions

Parentheses are only used for grouping and can be dropped if we assume the following syntactic precedences: (r ) before r* before r+s

Both binary operations are associative, so we don’t care how they associate.

We will use r+ as shorthand for rr*, i.e., denoting concatenation of 1 or more strings from r .

Q: What is r+ + ε ?

Similarly, we will use rk = r r r r … r

Examples of Regular Expressions

Let Σ= {0,1}

0*10*={w | w contains a single 1}

Σ*1Σ* = { w| w contains at least one 1}

(ΣΣ)* = {w | the length of w is even }

What is (01+)?

What is 0Σ*0 U 1Σ*1 U 0 U 1

Chapter 7: Regular Expressions
Exercises page 85  exercise1,  page 89  exercise 8

Chapter 8: Regular Expression Applications

Use egrep to find   all numbers divisible by 4 in the file http://paprika.umw.edu/~ernie/cpsc326/numbers

or /users/ernie/public_html/cpsc326/numbers

got to /users/ernie/public_html.cpsc230

Which lines in /users/ernie/public_html/sum.cpp have in-line comments?

Which lines are comments?

Use Java to do the same

## Class 4. Summer 2012

May 23rd, 2012

Go over the definition of NFA.

Power set.

Chapter 5: Nondeterministic Finite Automata

Do some exercises. Page 54. #2  pg 55 #4,5. Page 57 10

Chapter 6
The subset construction page 65
Convert NFA to DFA. theorem says NFA same as DFA
A language L is L(N) for some NFA N off L is a regular language.

Chapter 6: NFA Applications
Page 71, #3 Page 72 #5

Chapter 7. Regular Expressions
Formal Definitions
Concatenation of languages
Kleene closure
{a,b}*

A regular expression is a string r that denotes a language L(r) over some alphabet  S. The six kinds of regular expressions and languages…..
Page 76 .. 77

Examples pg 77-78
Regular Expression. —> Regular Language —-> Regular Expression

From another source:

Let Σ be a fixed alphabet.

A regular expression, or regexp for short, is an expression that describes a particular language over Σ.

If r is a regular expression, we write L(r ) for the language described by r .

We may also just use the regexp itself in place of the language it describes.

Primitive (atomic) regular expresions are:

• Φ describes the empty language L(Φ) = Φ;
• ε describes the language L(ε) = {ε } consisting of just the empty string; and
• a for a ε Σ describes the language L(a) = {a} consisting of just the string a of length 1.

Regular expressions can be combined with three possible operators: union, concatenation, and Kleene closure. If r and s are regexps, then so are:

• r+ s describing the language L(r ) U L(s);
• (rs), describing the language L(r )L(s);
• (r*) , describing the language L(r )*

Every regular expression is constructed by these rules; no other regular expressions are possible.

This is an inductive (recursive) definition, since it defined new regular expressions in terms of shorter ones (subexpressions).

Conventions

Parentheses are only used for grouping and can be dropped if we assume the following syntactic precedences: (r ) before r* before r+s

Both binary operations are associative, so we don’t care how they associate.

We will use r+ as shorthand for rr*, i.e., denoting concatenation of 1 or more strings from r .

Q: What is r+ + ε ?

Similarly, we will use rk = r r r r … r

Examples of Regular Expressions

Let Σ= {0,1}

0*10*={w | w contains a single 1}

Σ*1Σ* = { w| w contains at least one 1}

(ΣΣ)* = {w | the length of w is even }

What is (01+)?

What is 0Σ*0 U 1Σ*1 U 0 U 1

Chapter 7: Regular Expressions
Exercises page 85  exercise1,  page 89  exercise 8

## Class 3. Summer 2012

May 22nd, 2012

HW due today.

• Chapter 3, Exercise 7 using induction.

HW due Thursday.

• Exercise 2 at the end of Chapter 4, Page 43
• Turn in the source of your program along with the results of testing your program. The source code must contain complete and appropriate documentation.
• Testing is described next. Use the file /users/ernie/public_html/cpsc326/numbers
as input.
• For each input string, the output should be the input string followed by the word ACCEPTED if it is accepted by the DFA and NOT ACCEPTED if not.
• You can retrieve the file by http://paprika.umw.edu/~ernie/cpsc326/numbers or if you are logged into paprika use
cp /users/ernie/public_html/cpsc326/numbers  numbers to get a copy of numbers in your current directory.
• If you are on any system that has wget installed you can use
wget paprika.umw.edu/~ernie/cpsc326/numbers to retrieve a copy of the file.

Source code:

## Chapter 5, NFA

Suppose only list ‘legal’ transitions. Then we don’t get a DFA but we get what is  called a non-deterministic FA, or a NFA.

Consider the following. What statements are accepted?

Suppose we consider 00.

What can happen?

Is there ANY way 00 can be accepted?

Now consider .

What strings are accepted by this Finite Automata?

One other option to consider. Spontaneous transitions.

The accepted statements are …

Definition of NFA pages 50 and 51

Language accepte by a NFA defined on pages 52 – 53

## Class 2. Summer 2012

May 21st, 2012

Answer questions regarding material from Chapter 2

Go over HW.

Quiz on Chapter 1.

Chapter 3, start:

• closure properties
• induction proofs – read “Section 1.6: Principle of Mathematical Induction” By S.J. Farlow, University of maine
• Section 1.6: Principle fo Mathematical
• Practice with induction
• HW. Continue reading Chapter 3 and  practice some  of the Exercises that deal with induction proofs. Take a look at the videos:

HW – Pages 32 – 34 Exercises 1, 4, 6, 7, 9

Chapter 4

Source code:

HW. For Thursday. Exercise 2 on page..

## Class 1.

May 16th, 2012
CPSC 326
First Day.
This is also available at Google Docs – goals for CPSC 236

Two examples of proof.

Prove square root of 2 is not a rational number.

That is, prove it is not of the form p/q where p and q are integers, whole numbers

We will start by assuming it is, and show that making that assumption leads to a contradiction.

Suppose sqrt(2) is rational. That is assume sqrt(2) = p/q where p and q have no factors in common.

Then   2 = p2/q2.

So 2 p2 = q2.

So q2 is even so q*q = 2*k, so q must be even as well since the product of two odd numbers is odd

So q = 2*n.

Then 2 p2 = (2*n)*(2*n) = 4 n2 or p2 = 2n2. then p2 is even so p is even.

NOW p and q are both even so they have a factor in common, But that is ridiculous!!

Do one mathematical induction proof.

## Theoretical foundations of computing

• language
• automata
• grammar
• Turing machine
• Undecidability
• computability
• NP
• Complete, Hard

Why do we study these?
we study all these so that we can address the questions

• what does it mean for something to be computable?
• what can be computed?
• does it matter which language we use?
• what does it mean to find a tractable soluiton/algorithm?
• are there some solutions that cannot be simplified or made more efficient?

Our approach in this class is to go through the topics of the required book.

We begin with a definition of what we mean by a language, then study the notion of deterministic finite automata to consider certain classes of languages, then expand that to non-deterministic finite automata, and then more general notions for languages such as grammars and stack machines. This finally leads us to an abstract device called a Turing Machine. We then see that it is reasonable to define computability in terms of what that machine can handle or determine. A notion of undecidability comes out of that as well. we then look at complexity of algorithms to discuss what are tractable – solvable in a reasonable amount of time – problems. Then we can approach the issue as to whether there are some problems that are intractable.Suppose we want to compute  the nth power of x?
How long does that take?
Consider doing the problem by halving. Is that any faster?

How long does it take to factor a number into its prime factors?  One set of experts recently factored a 232-digit number in only 2 years on several hundred machines!! Is that a feasible or tractable solution? Factoring is an exponential problem – for now.

## Take a look at the topics in Chapter 1.

Sample quiz:

Name: ___________________ Score ___________________

Complete the  following  statements.

1. The ___________  ____________ of an alphabet S, written as  S*, is the set of all strings over  S.

2. An __________________________ is any finite set of symbols.

3. A ______________________ is a finite sequence of 0 or more symbols.

4. A _________________ is a set of strings over some fixed alphabet.

5. The _________________ of two strings  x and y is the string containing  all the symbols of x in order, followed by all the symbols of y in order.

Go over  various items in Chapter 2, CPSC 326 Powerpoint.

Including Finite State Machines

HW for next class.

Hand in in class.

Page 5 of the text. Prepare complete answers to exercises 1-4.

You are to do this work on your own. Let me know if you have questions.

Pages 16 – 19 of the text. Prepare complete answers to exercises 3, 5,6,8.