History and Memorization

Milestone Cards (already in chronological order):

• The Analytical Engine (Charles Babbage,
  19th century)

• Turing Machines (Alan Turing, 1936)

• Chomsky Hierarchy (Noam Chomsky, 1950s)

• Development of Regular Expressions (1950s)

• First Compiler (1950s)

• Applications in AI and NLP (present day)

Early computing devices, before the advent of modern electronic computers, faced significant limitations that shaped the development of automata theory. These limitations included:

• Mechanical Complexity: 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: 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: 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: 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: 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: 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: 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: 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.

In summary, the limitations of early computing devices spurred the development of automata theory in several ways:

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

• Memory: The exploration of different memory structures and their impact on computational power.

• Universality: The pursuit of general-purpose computing machines capable of performing a wide range of tasks.

• Formalization: The development of formal languages and grammars to describe the input and output of automata.

Characteristic of a regular language?

a) It can be described by a regular expression.

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

c) It can have an infinite number of strings.

Not Characteristic - It can contain strings with nested dependencies (like parentheses). Regular languages cannot have nested dependencies. Those require more powerful automata like pushdown automata.

A DFA is defined by a 5-tuple

a) A set of states

b) A start state

c) A set of accepting states

d) A set of transitions

Not part of 5-tuple : Production rules are associated with grammars, not DFAs.

DFA
For each state and input symbol, there is exactly one transition to another state. Determinism in a DFA means there's no ambiguity in how it processes input.

The purpose of an accepting stage in a DFA
To signal that the input string belongs to the language recognized by the DFA.

Non-deterministic Finite Automata

-            In NFA, given the current state there could be multiple next states

-            The next state may be chosen at random

-            All the next states may be chosen in parallel

What is Regular Language – if and only I some Finite State Machine recognizes it. It cannot store or count strings, very limited memory

1. The language of palindromes.

     Answer: NR. Palindromes require the DFA to "remember" the first half of the string to compare it to the second half. This requires an unbounded amount of memory, which DFAs don't have.

2. Strings with balanced parentheses (e.g., "(()())", "((()))()").

     Answer: NR. This requires keeping track of nested dependencies, which cannot be done with finite memory. You'd need a pushdown automaton to handle the potentially unbounded nesting.

3. All strings over {0, 1} that start with "101".

     Answer: R. This language has a clear pattern that can be easily described by a regular expression (101(0|1)*) and recognized by a DFA with a finite number of states.

4. Valid phone numbers in the format (XXX) XXX-XXXX, where X is any digit.

     Answer: R. This has a very specific, finite pattern that can be represented by a regular expression and a DFA.

5. Valid email addresses.

     Answer: NR. While simplified regular expressions can match most email addresses, the full specification allows for recursive patterns (e.g., nested comments), which DFAs cannot handle.

6.  Strings that contain the substring "aa" but not the substring "bb".

     Answer: R. This language can be broken down into simpler regular languages (strings with "aa", strings without "bb") that can be combined using regular operations (concatenation, union, etc.).

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

     Answer: NR. This requires unbounded counting to ensure there are always more 'a's than 'b's. A DFA cannot handle this.

8.   Strings where the number of 'a's is equal to the number of 'b’s.

     Answer: NR. This requires unbounded counting to compare the number of 'a's and 'b's, which is beyond the capability of a DFA.

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

     Answer: R. This can be represented by a DFA with a few states to keep track of the length (odd/even) and the last symbol encountered.

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

     Answer: NR. This language requires keeping track of the number of 'a's to ensure there's one more 'b'. This unbounded counting cannot be done with a DFA.