Theory of Computation (TOC)

• Theory of Computation (TOC) is a branch of computer science that deals with problem-solving efficiency on a computation model using algorithms.

TOC Branches

• Automata theory and languages.
• Computability theory.
• Complexity theory.

Automata Theory and Language

• Deals with the definitions and properties of computation's mathematical models, for example, computers.
• Examples of models include Finite Automata, Content-Free Grammars, and Turing Machines.

Computability Theory

• Focuses on what a model can and cannot compute

Complexity Theory

• It groups computable problems based on their hardness.

Main Purpose

• Develop formal mathematical models of computation that reflect real-world computers.

Basics

• Symbols are characters, e.g., a, b, c, ..., Z, 0, 1, 2, ..., 9, +, -, %, etc.
• Alphabets are finite, non-empty sets of symbols represented by Σ (sigma).
• For example, Σ = {0, 1} (binary alphabet), Σ = {a, b, ..., z} (lowercase letters), Σ = {+, -, %, /} (special characters).
• A string or word is a finite sequence of symbols from an alphabet.
  • Example: "011100110" from binary alphabet Σ={0,1}
  • Example: "aabbaacah" from alphabet Σ={a,b,c}

Empty String

• An empty string contains zero occurrences of a symbol and is denoted by "E" (Epsilon); it contains no symbols.

Length of a String

• Refers to the number of symbols/characters in the string/word, denoted by |w|.
• For example, if w = 01101101 from the binary alphabet Σ = {0, 1}, then |w| = 9

Concatenation

• An operation that joins two or more strings.
• Given x = a1a2...an and y = b1b2...bn, the concatenation of strings xy is a1a2...anb1b2...bn.
  • Example: If s = ababa and t = cdcddc, the concatenation of st = ababacdcddc.

Power of an Alphabet

• If "Σ" is an alphabet, you can express the set of all strings of a certain length from that alphabet.
• Denoted by Σk, which represents the set of strings of length k.
• Eg:- Σ = {0,1} has 2 Symbols.
  • Σ1 = {0,1}, (2^1 = 2) K=1
  • Σ^2 = 200,01, 10, 11}, (2^2=4) K=2
  • Σ3 = {000,001,010,011, 100, 101, 110,111}, (2^3 = 8) K=3
• The set of strings over an alphabet Σ is denoted by 2* = Kleen Closure.

Languages

• Defined as a finite set of non-empty strings.
• If Σ is an alphabet and L ⊆ Σ*, then L is a language.
  • Example: set of legal English words.
  • Example: a set of legal 'C' program
  • Example: {ε, 01, 0011, 000111...}

Kleene Closure

• Denoted as Σ* = {E,0,1,00,01,10,11,...}.
• Kleene Closure is defined as Σ* = Σ⁰ U Σ¹ U Σ² U Σ³ U… with E symbol.
• A set of Strings over an alphabet excluding E, is usually denoted as Σ+ (Kleene plus).
• Σ+ = Σ* - {E} = {0,1,00,01,10,11,...}.

Operations on Languages

• Complementation: Given a language L over an alphabet Σ, the complement of L, denoted by L', is Σ* - L.
• Union: Given languages L1 and L2 over an alphabet Σ, the union of L1 and L2, denoted by L1 U L2, is {x | x is in L1 or L2}.
• Intersection: Given languages L1 and L2 over an alphabet Σ, the intersection of L1 and L2, denoted by L1 ∩ L2, is {x | x is in L1 and L2}.
• Concatenation: Given languages L1 and L2 over an alphabet Σ, the concatenation of L1 and L2, denoted by L1 . L2, is {w1w2 | w1 is in L1 and w2 is in L2}.
  • Example: L1 = {a, ba}, L2 = {bcb, b} L1.L2= {abcb, ab, babcb, bb}
• Reversal: Given a language L over an alphabet Σ, the reversal of L, denoted by Lr, is { wr \ w is in L }.
  • Example: Given L={a, ba, cba}, LR = {a, ab, abc}
• Kleene's closure: Given a language L over an alphabet Σ, the Kleene’s closure of L, denoted by L*, is { x | for any integer n >=0 }. Example: Given L* = ∪ Li.
• Positive closure: Given a language L over an alphabet Σ, the positive closure of L, denoted by L+, is { x | for any integer n >= 1}. Example: Given L+ = ∪ Li.
• Symbol is a character.
  • Symbol examples: a, b, c…Z, 0,1, 2, …9 , +,-,%, etc.
• Alphabet *∑*is a finite, non-empty set of symbols.
  • Alphabet examples
• Σ = {a , b}.
• Σ = {0, 1}
• String over an alphabet ∑ is a sequence of Symbols. For example, string s = aabba. A string s is a sequence of symbols which can be created and chosen from alphabets.

Automata

• Automata Theory deals with the logic of computation with respect to simple machines, referred to as automata.
• An automaton is an abstract model of a digital computer
• An automaton with a finite number of states is called a Finite Automaton (FA) or Finite State Machine (FSM).

Finite Automaton

• Examples can be Finite Automata.
• L = Set of all strings of length "2"
• Laa, ab, ba, bb }.
• W1 = ab finite.
  • Can easily check "Belongs to the Language".
• W2 Finite = bbb.
  • Can easily check "Not belongs to the Language". -WEL or WAL String ○ FA Present in language or NOT § inputs =YES § FA = No

Finite Automata Definition

• Is an abstract computing device and a mathematical model of a system with discrete inputs, outputs, states, and transitions.
• Transitions occur from state to state on input symbols from alphabet Σ.
• Finite Automata (FA) representations:
  • Graphical (Transition diagrams)
  • Tabular(Transition table)
  • Mathematical(Transition Function or Mapping Function)

Formal Definition of FA

• Are 5 tuples M =(Q, Σ, δ, qo, F) Where - Q = finite set called states - Σ= finite set called alphabets - δ = Q x Σ →Q is the transition funtion -q0 𝞊 Q the start state(Initials state) - F ⊆ Q is the set of accept state (Finalstate)

Transition Diagrams

• Directed graphs are associated with automata. vertices of the connected graph. It corresponds to "the state" of the Finite Automata. Ex: {0,1} → inputs -q0 -q1 → intermediate state -q2 → final state

Properties of FA

• A row corresponds to state.
• Columns correspond to /p Symbols.
• Tables correspond to Next states.
• The "start state" is marked with an arrow → start State The Accept State is marked by a "star" ⭐ state example : ⭐q0 ⭐q1

Mapping function

• 8(Currentstate, Currentinput Symbol) = Next State. S(q0, a ) =q1
• Transition Function - The mapping function or "Transition Function" is denoted by δ. Two parameters are "passed to the transition function".
• Current State Input Symbol The transition function (TC) then returns a state
• which can be called a "NextState" denoted by Qx Σ→ Q. Transitions : Can describe "operations". "Finite Automata" is base "For the formal "languages.

Automata Applicaitons

• Compiler Design
• Switching design and theory/digital circuit analyis
• Complex softwares and hardwares
• Can describe the correctness of your steps
• Can design finite state machines

Types of Finite Automata

• Finite automata with or with out a particular output for a particular input.
  • Finite Automata without output.
• has DFA state and NFA state
• Finite Automata with output
• has Moore M/C and Mealy M/C

DFA vs NDFA vs E-NFA

- DFA is a Deterministic Finite Automata 
- NDFA is a Non-Deterministic Finite Automata. 
- E-NFA has Non-Deterministic FA; has E-moves ,or Epsilon

Deterministic Finite Automata

• Finite automata machines only read symbols on string at one time
• Is “ the Uniqueness” of the Computation
• In DFA" there is all the only one path for steps and “input" that from “ the Current State" all to "then next step". Can “ have only one path" ->( the state is a "Current state" to and new state for the all given types steps only single state for the steps single parth)

• all DFA step by step with the move ,ie cannot change state without any charater

• ( D.F.A ) is a State with lexical analysis in Compiler can Contain more than one start state.

• formal language of DFA: Collection State or Tuples are is Same. The State diagram is a ( Graph), called a "State Machine diagram" can be (graphically) represent D.F.A by. Transition: labeled is and is an with "arc input Character". To show the transition is Marked. The initial State is Marked with the double arrows