AI 100 | Chapter 4 Concept Deck

McCulloch-Pitts Neurons & Finite Automata

From one binary decision to a machine that remembers a sequence.

Neuron = weighted yes/no decision. Automaton = finite memory updated one symbol at a time.

Book Ch. 4 Lectures 9/8, 9/10, 9/15 Review Q22-26, 30, 33, 36-44 Theory Q1-16

Use the arrow keys, Space, or the buttons to navigate

Mental model

Three levels of computational power

Boolean circuit

Question: What output follows from the current input?

Memory: None

Neural analogy: Feedforward network

Finite automaton

Question: What state follows from the old state and current symbol?

Memory: One of finitely many states

Neural analogy: Recurrent network

Turing machine

Question: What can be computed with writable external memory?

Memory: Unbounded tape

Relation: Automaton + external memory

Review Q43-44 Lecture 9/15

Prerequisite

Boolean logic is the neuron’s vocabulary

A	B	AND	OR	XOR
0	0	0	0	0
0	1	0	1	1
1	0	0	1	1
1	1	1	1	0

AND: all required conditions are true.
OR: at least one condition is true.
NOT: flips 0 and 1.
XOR: inputs differ.
{AND, OR, NOT} is complete: together they can express every Boolean function.

Evaluate parentheses and NOT first, then AND, then OR.

Review Q22-25 Theory Q1-3 Lecture 9/8

McCulloch-Pitts neuron

A weighted vote followed by a threshold

s = Σ_i=1^M w_ix_i

y = 1 if s ≥ θ; otherwise y = 0

Inputs x_i

Binary facts: each is 0 or 1.

Weights w_i

Positive encourages firing; negative inhibits it.

Threshold θ

The minimum weighted sum needed to output 1.

Exam trap: the weighted sum can be 2 or 3, but the neuron’s output is always only 0 or 1.

Review Q30 Theory Q4

Calculation routine

Never guess: use the same four steps

Multiply each input by its weight.
Add the products to obtain s.
Compare using s ≥ θ.
Return the binary output y.

Worked example

x₁=0, x₂=1; w₁=w₂=1; θ=1

s=(1)(0)+(1)(1)=1

1 ≥ 1 ⇒ y=1

Review Q30 answer: B (output 1)

Review Q30 Theory Q4

Canonical neuron 1

AND requires both votes

w₁=1, w₂=1, θ=2

The maximum sum is 2. Therefore, the neuron fires only when both inputs are 1.

This neuron computes AND. Review Q26 answer: B.

x₁	x₂	s	s ≥ 2?	y
0	0	0	No	0
0	1	1	No	0
1	0	1	No	0
1	1	2	Yes	1

Review Q26 Theory Q5 Lecture 9/8

Canonical neurons 2-3

OR needs one vote; NOT uses inhibition

OR

w=(1,1), θ=1

Any single input of 1 reaches the threshold.

00 → 0; 01, 10, 11 → 1

Theory Q13: w₁=w₂=1, θ=1.

NOT

w=-1, θ=-0.5

x=0: s=0 ≥ -0.5 ⇒ y=1

x=1: s=-1 < -0.5 ⇒ y=0

Theory Q6: weight -1, threshold -0.5.

Course convention: use θ=-0.5 for NOT. The book’s θ=0 also works for binary input under the ≥ rule.

Theory Q6, Q13 Review Q30 reinforces OR

Threshold behavior

A 2-of-3 majority neuron

w=(1,1,1), θ=2

Inputs	Sum	Output
000	0	0
001, 010, 100	1	0
011, 101, 110	2	1
111	3	1

The threshold divides all possible inputs into two groups:

Weighted sum below 2 → output 0
Weighted sum at least 2 → output 1

A threshold is a decision boundary.

Theory Q4 Lecture 9/8

Limitation

Why one neuron cannot compute XOR

x₁	x₂	XOR
0	0	0
0	1	1
1	0	1
1	1	0

A single threshold unit creates one straight decision boundary.

For XOR, the two positive points are diagonally opposite. No one line separates them from both negative points.

XOR and XNOR are not linearly separable, so one threshold neuron is insufficient.

Review Q25-26 concept link Lecture 9/8

Networks

Multiple neurons solve what one neuron cannot

XOR = (x₁ OR x₂) AND NOT(x₁ AND x₂)

Layer 1A

Compute x₁ OR x₂.

Layer 1B

Compute NOT(x₁ AND x₂).

Layer 2

AND the two intermediate results.

AND, OR, and NOT are functionally complete, so a suitable network can implement any Boolean function.

Review Q25 Theory Q5, Q6, Q13

Neuron question checkpoint

What the official questions are testing

Question

Skill

Answer cue

Review Q26

Identify gate from weights/threshold

(1,1), θ=2 ⇒ AND (B)

Review Q30

Calculate one neuron output

s=1 ≥ 1 ⇒ output 1 (B)

Theory Q4

State firing condition

Σw_ix_i ≥ θ

Theory Q5

Design AND neuron

w=(1,1), θ=2

Theory Q6

Design NOT neuron

w=-1, θ=-0.5

Theory Q13

Design OR neuron

w=(1,1), θ=1

Full-credit calculation: products → weighted sum → threshold comparison → binary output.

Finite automata

A machine with a small, fixed memory

Begin in the start state.
Read one input symbol.
Follow that symbol’s transition.
Repeat until the entire finite string is read.
Accept iff the final state is accepting.

The state is the memory

The machine does not store the whole input. Its current state summarizes only the past information relevant to the task.

next state = f(current state, current symbol)

Theory Q7-8 Review Q33, Q38 Lecture 9/10

Diagram language

Read the symbols before tracing

Start

An arrow from nowhere marks the start state.

Accept

A double/concentric circle marks an accepting state.

Transition

The edge label tells which input causes the move.

Review Q33 answer: C — a double (concentric) circle.

Review Q33 Theory Q8

Core example

Remember whether the number of 1s is odd

Reading 1 toggles: even becomes odd; odd becomes even.

Reading 0 loops: it does not change the number of 1s.

Theory Q9, Q10, Q14 Lecture 9/10

Trace, do not eyeball

Does the odd-1s machine accept 11010?

EVEN→ 1ODD→ 1EVEN→ 0EVEN→ 1ODD→ 0ODD

Read	Old state	New state
1	Even	Odd
1	Odd	Even
0	Even	Even
1	Even	Odd
0	Odd	Odd (accept)

Yes. It ends in the accept state. Theory Q9 answer: accepted; Q14: 10 is also accepted.

Theory Q9, Q14 Review Q38

Language and termination

What does the machine accept?

Language

The language is the set of all strings accepted by the machine.

Odd-1s examples: 1, 10, 01, 111, 11010.

Finite-automaton languages are called regular languages.

Infinite ordinary input

The machine decides only when the input ends.

If the string never ends, it continues changing states and never produces the ordinary final accept/reject decision.

Passing through an accept state early is not enough. Acceptance depends on the final state after the entire finite input.

Theory Q7, Q8, Q10, Q11 Review Q38

Counting with finite state

Multiples of 3 require only three states

Let each state remember the number of 0s modulo 3:

q₀: remainder 0 — accepting
q₁: remainder 1
q₂: remainder 2

Reading 0 advances q₀→q₁→q₂→q₀. Reading 1 loops.

How to identify the language

Determine what each state summarizes.
See which symbols change that summary.
Interpret the accepting state.

Review Q36: number of 0s is a multiple of 3 (A).

Review Q36 Lecture 9/10

Counting progress

At least three a’s

States 0,1,2 record progress. State 3 means “at least three a’s have occurred.”

Theory Q12: minimum 3 a’s. Review Q37: baba ends at state 2 and is accepted (C).

Review Q37 Theory Q12

Designing an automaton

Accept exactly 101 — and nothing else

q0 --1→ q1 --0→ q2 --1→ qA

Each state means “this much of 101 has been matched.”

q0: nothing matched
q1: matched 1
q2: matched 10
qA: matched exactly 101

The missing piece: sink state

Every wrong symbol goes to a rejecting sink qD.

Any extra symbol after qA also goes to qD.

qD loops on both 0 and 1.

A chain showing only 1,0,1 is an illustration, not a complete DFA, unless all omitted transitions are defined.

Theory Q16

Official tracing questions

Use a state table for Review Q39-41

Review Q39

Trace input 100101 from start A.

Final: C, accepted.

Answer A

Review Q40

Test each candidate until one finishes in D.

Accepted: 0100101.

Answer D

Review Q41

A and B accept; D is a rejecting trap.

Accepted: 1010.

Answer A

Write one row per symbol: symbol | old state | new state. Judge only the final state.

Review Q39-41 Theory Q9, Q14, Q15 Lecture 9/15

Limits of finite memory

What finite automata can and cannot remember

Can recognize

Odd/even count
Count modulo 3
Ends with 01
Contains 101
At least three a’s

Cannot generally recognize

Arbitrarily balanced parentheses
0ⁿ1ⁿ for arbitrary n
Arbitrary palindromes
Exact unbounded counts

A finite number of states can remember only a finite set of summaries.

Theory Q7, Q11 Lectures 9/10, 9/15

From finite automaton to Turing machine

External writable memory changes the model

Finite automaton

Reads one symbol at a time and changes finite state.

Cannot rewrite input or revisit arbitrary stored information.

Turing machine

Adds an effectively infinite tape and a read/write head.

Can write symbols and move left or right.

finite automaton + external read/write memory = Turing machine

Review Q43: C. Review Q44: C — write on tape and move the head left/right.

Review Q43-44 Lecture 9/15

The conceptual bridge

How neurons implement an automaton

Use one neuron (or bit pattern) to represent each state:

E_t=1: currently even
O_t=1: currently odd
I_t: current input symbol

O_t+1=(E_t AND I_t) OR (O_t AND NOT I_t)

E_t+1=(E_t AND NOT I_t) OR (O_t AND I_t)

Feed the state outputs back as inputs at the next time step. That feedback creates finite memory: a recurrent network.

Review Q25, Q43 Theory Q4-16 concept link

Complete exam map

Every relevant official question

Concept

Review questions

Theory questions

Boolean foundation

Q22 truth rows; Q23 contradiction; Q24 iff; Q25 completeness

Q1-3 expression evaluation

MP rule/calculation

Q26 identify AND; Q30 calculate output

Q4 firing rule

MP gate design

Q25 completeness supports networks

Q5 AND; Q6 NOT; Q13 OR

FA notation/language

Q33 accept symbol; Q36 language; Q38 final-state rule

Q7 language; Q8 accept state

FA tracing

Q37 and Q39-41

Q9 trace 11010; Q10 examples; Q12 count a; Q14 trace 10; Q15 trace 11

FA edge cases/design

Q38 final state

Q11 infinite input; Q16 exactly 101

FA vs TM

Q43 external memory; Q44 tape/head

Conceptual extension

Study priority: master the procedure, then use the question number as a retrieval cue.

Final checklist

What you should be able to do without notes

McCulloch-Pitts

Compute s=Σw_ix_i
Apply s ≥ θ
Construct AND, OR, NOT
Explain why XOR needs a network

Finite automata

Identify start and accept states
Trace one transition per symbol
Describe the accepted language
Design progress and sink states

Neuron: current-input decision. Automaton: old-state + current-input decision. Recurrent neural network: neurons whose outputs become the next state.

Relevant Review Q22-26, 30, 33, 36-44 covered Theory Q1-16 covered

McCulloch-Pitts Neurons & Finite Automata

Three levels of computational power

Boolean circuit

Finite automaton

Turing machine

Boolean logic is the neuron’s vocabulary

A weighted vote followed by a threshold

Inputs xi

Weights wi

Threshold θ

Never guess: use the same four steps

Worked example

AND requires both votes

OR needs one vote; NOT uses inhibition

OR

NOT

A 2-of-3 majority neuron

Why one neuron cannot compute XOR

Multiple neurons solve what one neuron cannot

Layer 1A

Layer 1B

Layer 2

What the official questions are testing

A machine with a small, fixed memory

The state is the memory

Read the symbols before tracing

Start

Accept

Transition

Remember whether the number of 1s is odd

Does the odd-1s machine accept 11010?

What does the machine accept?

Language

Infinite ordinary input

Multiples of 3 require only three states

How to identify the language

At least three a’s

Accept exactly 101 — and nothing else

The missing piece: sink state

Use a state table for Review Q39-41

Review Q39

Review Q40

Review Q41

What finite automata can and cannot remember

Can recognize

Cannot generally recognize

External writable memory changes the model

Finite automaton

Turing machine

How neurons implement an automaton

Every relevant official question

What you should be able to do without notes

McCulloch-Pitts

Finite automata

Inputs x_i

Weights w_i