History and Memorization

Analytical Engine

First Milestone by Charles Babbage in 19th Century

Turing Machines

Second Milestone by (Alan Turing, 1936)

Chomsky Hierarchy

Third Milestone by Noam Chomsky, 1950s

Development of Regular Expressions

Fourth Milestone on 1950s

First Compiler (1950s)

Fifth Milestone on 1950s

Applications in AI and NLP

Present Milestone

Mechanical Complexity

Limitation. Early computers were often mechanical, relying on gears, levers, and other physical components. This made them complex to build, prone to errors, and limited in speed and scalability.

Influence

Limitation. This led to a desire for simpler, more abstract models of computation, like Turing machines, which could be studied theoretically without the constraints of physical implementation.

Limited Memory

Limitation. Early computers had very limited memory capacity, often relying on punched cards or paper tape. This restricted the complexity of programs they could execute and the amount of data they could process

Influence

Limitation. This spurred the development of theoretical models with different memory structures, such as finite automata with limited memory and pushdown automata with stack-based memory, to understand the capabilities and limitations of different memory organizations.

Lack of Flexibility:

Limitation. Many early computers were designed for specific tasks, like calculating mathematical tables or cracking codes. They lacked the flexibility to be easily reprogrammed for different purposes.

Influence

Limitation. This motivated the development of the concept of a universal Turing machine, a theoretical machine capable of simulating any other Turing machine, highlighting the possibility of general-purpose computation.

Manual Input/Output

Limitation. Early computers often relied on manual input and output methods, such as punched cards or printed results. This made interaction with the machine slow and cumbersome.

Influence

Limitation. This led to the development of formal languages and grammars to describe the input and output of automata, providing a more structured and efficient way to interact with these theoretical machines.

Abstraction

Development. The need for simpler, more abstract models of computation that were not limited by physical constraints.

Memory

Development. The exploration of different memory structures and their impact on computational power

Universality

Development. The pursuit of general-purpose computing machines capable of performing a wide range of tasks

Formalization

Development. The development of formal languages and grammars to describe the input and output of automata.

Regular Language

It can be described by a regular expression.

Regular Language

It can be recognized by a deterministic finite automaton (DFA)

Regular Language

It can have an infinite number of strings

Characteristic of a regular language

DFA

For each state and input symbol, there is exactly one transition to another state

Non-deterministic Finite Automata

given the current state there could be multiple next states

Non-deterministic Finite Automata

The next state may be chosen at random

NFA

All the next states may be chosen in parallel

Stephen Kleene

Developer of Regular Expression

Chomsky hierarchy

a system for classifying formal grammars

Turing machine

a mathematical model of a computer that manipulates symbols on a tape

Turing Machine

a mathematical model of a computer that manipulates symbols on a tape

NR

Identify if R or NR. The language of palindromes

NR

Identify if R or NR. Strings with balanced parentheses (e.g., "(()())", "((()))()").

R

Identify if R or NR. All strings over {0, 1} that start with "101"

R

Identify if R or NR. Valid phone numbers in the format (XXX) XXX-XXXX, where X is any digit

NR

Identify if R or NR. Valid email addresses

R

Identify if R or NR. Strings that contain the substring "aa" but not the substring "bb"

NR

R or NR. Strings with more 'a's than 'b's (e.g., "aaab", "aabaa")

NR

R or NR. Strings where the number of 'a's is equal to the number of 'b’s.

R

R or NR. All strings over {a, b, c} that have an odd length and end with "a".

NR

R or NR. Strings over {a, b} of the form (a^n) (b^(n+1)), where n >= 0