Manav Goyal

Theory Of Computation - Others

Table of Contents

Regular Language and Finite Automata

Language

  • Symbol
  • Alphabet (βˆ‘)
    • An alphabet is a finite, non-empty set of Symbols
      • {0, 1} is a binary alphabet -=> Given by default
      • { A, B, …, Z, a, b, …, z} is an English alphabet
    • Powers of an Alphabet
  • String -=> Collection of Alphabet, sequence
    • A string over an alphabet βˆ‘ is a sequence of any number of symbols from βˆ‘
    • Empty String -=> An empty string, denoted by Ι›, is a string containing no symbol -=> Ι› is a string over any alphabet
    • Length of String -=> -=> It is the number of symbols present in a string (Denoted by |S|)
  • Operations on Strings
    • Concatenation
      • The concatenation of strings x and y, denoted by x.y or xy, is a string z such that
      • automata.computation = automatacomputation
    • Substring
      • Let x and y be strings over an alphabet Ξ£. The string x is a substring of y if there exist strings w and z over Ξ£ such that y = w x z
      • Ξ΅ is a substring of every string
      • For every string x, x is a substring of x itself
    • Reversal
      • The reversal of the string x, denoted by xr, is a string such that if x is Ξ΅, then xr is Ξ΅ and other condition
      • βˆ‘* -=> The set of strings created from any number (0 or 1 or …) of symbols in an alphabet βˆ‘
      • βˆ‘+ -=> The set of strings created from at least one symbol (1 or 2 or …) in an alphabet βˆ‘
  • Language -=> Collection of String
    • Length of Language -=> Can be infinite
  • Operations on Languages
    • Complementation
    • Union
    • Intersection
    • Concatenation
    • Reversal
    • Closure
      • Kleene’s closure/star
      • Kleene’s closure/plus

Automata (Machine)

  • Mathematical Model/Machine to find of the given String is part of the Language
    • Not possible to find it in case of infinite Length by brute force method
  • Finite Automata (FA)
    • The finite automata or finite state machine is an abstract machine that has five elements or tuples. It has a set of states and rules for moving from one state to another but it depends upon the applied input symbol
    • Finite Automata
    • Transition Diagram and Function
    • Language that FA accept are called Regular Language
    • Data Set -=> Regular expression to NFA > NFA to DFA > DFA Compression > Matching on DFA
  • Types
    • Finite Automata (FA)
    • Pushed Down Automata (PDA)
    • Linear Bound Automata (LBA)
    • Turing Machine (TM)
  • Power of βˆ‘
    • βˆ‘0 -=> Set of all Strings with length 0 = Ι› or Ξ» -=> Null String -=> Contains identity element
    • βˆ‘1 -=> Set of all Strings with length 1
    • βˆ‘2 -=> βˆ‘.βˆ‘
    • βˆ‘* -=> Kleene Closure -=> Set of all Strings of all length possible -=> Infinite Language = (a+b)* -=> Total 2n possibility
    • βˆ‘+ -=> All Strings except βˆ‘0 = βˆ‘* - Ι›

Grammar

  • A Grammar can be regarded as a device that enumerates the sentences of a Language
  • Give you the generated Language
  • A grammar G is defined as quadruple -=> G = {V, T, P, S}
    • Variable -=> Can repeat, In capital letter
    • Terminal -=> Terminate, In small letter
    • Production -=> Rules
    • Start -=> To start
  • Can check if the given String is part of that Language

Chomsky Hierarchy

  • Type 0 -=> Unrestricted Grammar (UG)
    • Recursively Languages (RE) -=> Turing Machine (TM)
    • Recursively Enumerable Languages (REC) -=> Halting Turing Machine (HTM)
      • Power of DTM ≑ NTM
      • Adding 1 Stack to PDA creates TM
      • Adding 1 Tape to FA creates TM
      • Turing Machine (TM) -=> Halting, Non-halting, Hanging, Deterministic, Non-Deterministic TM
  • Type 1 -=> Context Sensitive Grammar (CSG)
    • Context Sensitive Language (CSL) -=> Linear Bound Automata (LBA)
  • Type 2 -=> Context Free Grammar (CFG)
    • Context Free Language (CFL) -=> Non-Deterministic Push Down Automata (NPDA)
    • Deterministic Context Free Language (DCFL) -=> Deterministic Push Down Automata (DPDA)
      • Power of NPDA > DPDA
      • Adding 1 Stack to FA creates PDA
  • Type 3 -=> Regular Grammar (RG)
    • Regular Language (REG) -=> Finite Automata (FA)
      • Power of DFA ≑ NFA
      • FA have limited memory
      • NFA is used to accept Infinite REG
      • x β†’ y, x ∈ V, y ∈ T*V + T* or VT* + T* -=> Left linear or Right linear
  • Grammar
  • Power -=> FA < DPDA < PDA < LBA < TM

DFA

  • Deterministic Finite Automata (DFA) = {Q, βˆ‘, 𝛿, qo, F} -=> Single choice of move after applying a Symbol
    • Q -=> Set of finite states
    • βˆ‘ -=> Set of Alphabet
    • 𝛿 -=> Transition -=> 𝛿: Q x βˆ‘ β†’ Q
      • If you apply any input symbol then where will it go
    • qo -=> Start
    • F -=> Set of finite final states -=> F βŠ† Q
  • Construct/Design DFA
  • Taking Complement of DFA -=> Make final β†’ non-final & non-final β†’ final states
  • Minimum States = Length of Minimum String + 1

NDFA

  • Non-deterministic Finite Automata (NFA) = {Q, βˆ‘, qo, F, 𝛿} -=> Multiple choice of move after applying a Symbol
    • Q -=> Set of finite states
    • βˆ‘ -=> Set of Alphabet
    • qo -=> Start
    • F -=> Set of finite final states -=> F βŠ† Q
    • 𝛿 -=> Transition -=> 𝛿: Q x βˆ‘ β†’ 2Q
  • Used to check weather a Regular language is accepted by a machine or not -=> NFA is easier to be implemented as compared to DFA
  • DFA vs NFA
  • Thompson Construction -=> Regular expression to NFA
    • First we have to design its Regular expression
  • Conversion of NFA to DFA
    • Create Transition Table of NFA
    • Create Transition Table of DFA from NFA TT
      • Copy first row, then expand other states
      • Initial state same and final state will be all states that contains final state of NFA
      • If NFA contains n states then DFA will contain maximum of 2n states
  • Ι›-NFA (Epsilon NFA)
    • NFA with epsilon transitions to NFA without epsilon transition -=> Eliminating Ι›-moves
    • Ι›-NFA = {Q, βˆ‘, F, 𝛿, qo}
      • Q -=> Finite set of states
      • βˆ‘ -=> Input Symbol (Alphabet)
      • F -=> Set of final states
      • 𝛿 -=> Transition Function -=> 𝛿: Q x (βˆ‘ βˆͺ Ι›) β†’ 2Q
      • qo -=> Start state
    • Steps
      • Find all edge starting from S2
      • Duplicate all edges to S1 without changing edge labels
      • If S1 in initial state, make S2 initial also
      • If S2 in final state, make S1 final also
      • Remove dead state
  • Limitations of FSA
    • Limited Memory
      • Generally used for Regular Languages -=> Finite
    • Strings without Comparison
      • No comparison between Powers
    • Linear Power
  • Application of FSA
    • Word Processor Program
    • Digital Logic Design
    • Lexical Analyzer
    • Switching Circuit Design
    • Text Editors
    • Software for scanning large bodies of text such as Web pages to find occurrence of words, phases, patterns, etc
    • Software with finite states like Vending machines, Weigh machine, Traffic lights, Toll machines, etc
    • Game design like PacMan, Treasure Hunt, etc
  • Minimization of DFA
    • Make TT from Diagram if not given
      • Mark start and final states in TT
      • Remove unreachable states
    • Convert states into equivalent classes
      • Make one group of accepting states (final) and non-accepting states (non-final) -=> Ο€0
      • Check and Separate every two symbols if the any outputs leads to a Symbol of different groups -=> Ο€1
      • Check again like before, this time by referencing Ο€1 -=> Ο€2
    • Now the number of remaining groups represents new states, Create the Transition Diagram
  • Equivalence of NFA and DFA

Mealy & Moore

Moore Machine (Mo)

  • Mo = {Q, βˆ‘, βˆ†, 𝛿, Ξ», qo}
    • Q -=> Finite set of states
    • βˆ‘ -=> Input Symbol (Alphabet)
    • βˆ† -=> Output Symbol
    • 𝛿 -=> Transition Function -=> 𝛿: Q x βˆ‘ β†’ Q
    • Ξ» -=> Output function -=> Ξ»: Q β†’ βˆ†
    • qo -=> Start state
  • If input is of length n, then output will be of length n+1
  • Transition Table
    Current State Next State Output
    Input = a | Input = b
    qo - -

Mealy machine

  • Me = {Q, βˆ‘, βˆ†, 𝛿, Ξ», qo}
    • Q -=> Finite set of states
    • βˆ‘ -=> Input Alphabet -=> Format = input/output
    • βˆ† -=> Output Symbol
    • 𝛿 -=> Transition Function -=> 𝛿: Q x βˆ‘ β†’ Q
    • Ξ» -=> Output function -=> Ξ»: Q x βˆ‘ β†’ βˆ†
    • qo -=> Start state
  • Output of state depends on input
  • If input is of length n, then output will be of length n
  • Transition Table
    Current State Next State Output
    Input = a | Input = b
    State | Output | State | Output
    qo - -
  • Difference between Mealy and Moore
    • Mealy vs Moore

Conversion

  • Moore to Mealy Conversion
    • m state & n output to maximum m state
    • From Transition Diagram
      • Write all the states
      • Write transition of each state same as Moore and output will be of state pointing towards
    • From Transition Table
      • Write all the columns from Moore TT except output column
      • Write output corresponding to each transition equal to the output of the state it represents
  • Mealy to Moore Conversion
    • m state & n output to maximum m x n state
    • From Transition Diagram
      • Start from starting state
      • Write transition corresponding to each input and write its output next to the state it is pointing towards
      • If output conflict than create a duplicate state with new output
      • Complete all input transition for all states, even the duplicates

Regular Expression

  • Method to represent a language (Regular Languages)
  • Let R be a Regular expression over βˆ‘ if R is
    • R = Ι› -=> L(R) = {Ι›}
    • R = Ξ¦ -=> L(R) = {}
    • R = a -=> L(R) = {a}
    • R1 βˆͺ R2 = Regular -=> Union
    • R1 . R2 = Regular -=> Concatenation
    • R* = Regular -=> Kleene Closure
    • If R is regular then (R) is also regular
  • FA to regular expression and regular expression to FA
    • Arden’s Theorem -=> Find a regular expression of a Finite Automaton
  • Regular Expressions for Finite Languages
    • No String -=> L = {} -=> Ξ¦
    • Length 0 -=> L = {Ι›} -=> Ι›
    • Length 1 -=> L = {a, b} -=> (a + b)
    • Length 2 -=> L = {ab, ba, aa, bb} -=> (ab + ba + aa + bb) = (a + b)(a + b)
    • At most 1 -=> L = {Ι›, a, b} -=> (Ι› + a + b)
    • At most 2 -=> (Ι› + a + b)(Ι› + a + b)
  • Regular Expressions for Infinite Languages
    • Symbols Used
      • βˆ‘ -=> Single 0/1
      • βˆ‘* -=> Any number of 0/1
      • 1* -=> Any number of 1
      • βˆ‘+ = βˆ‘* - Ι› = βˆ‘βˆ‘*
    • All String having single "b" -=> a*ba*
    • All String having at least one "b" -=> (a+b)*b(a+b)*
  • Pattern matching and regular expressions
  • Regular grammar and FA
  • Pumping lemma for regular languages
    • To check weather the language is regular or not
    • It is a negative test
      • If Language fails PLT then it is not regular
      • If Language passes PLT then it is not decidable
    • If L is a infinite language then there exists some positive integer "n" (Positive length) such that any string W ∈ L has length greater than equal to "n", |W| >= n then W can be divided into three parts, W = xyz satisfy following conditions
      • For each i >= 0, xyiz ∈ L
      • |y| > 0
      • |xy| <= n

Closure Properties of Regular Languages

  • Closure Property of RL
  • Reversal
    • Make initial state of M as final state of M
    • Final state of M became initial state of M
    • Reverse the direction of edges of M to make M
    • No change in loop and remove unnecessary states
  • Homomorphism
    • Substitution Function
    • Homomorphism
    • Inverse Homomorphism
      • Inverse Homomorphism
      • Homomorphism of Inverse Homomorphism of a Language is subset of original Language
  • Quotient Operation
    • Left Quotient (Cut Prefix)
    • Right Quotient (Cut Suffix)
    • Quotient Operation
  • INIT (Initial/Prefix)
    • Set of all Prefix of W ∈ L
    • If making DFA for INIT then at last make all non-final states as final except traps
  • Infinite Union
    • Regular expression are not closed

Context Free Grammars

Context-Free Grammar (CFG)

  • CFG = {V, T, P, S}
    • Variable (V) -=> Finite set of variables (Non Terminal)
      • Denoted by capital letter
      • Can substitute Variable or Terminal
    • Terminal (T) -=> Finite set of terminals (V ∩ T = Ξ¦)
      • Denoted by small letter
      • Cannot substitute anything
    • P -=> Production rules (Substitution Rules)
      • Ξ± β†’ Ξ²
      • Only one variable in left hand side
    • S -=> Start variables
      • Symbol at first
  • Convert CFL to CFG
  • Derivation -=> Generating String from CFG or If a particular String belongs to that language
    • LMD -=> Substitute left most variable first while creating tree
    • RMD
  • Derivation Tree
    • Parse Trees
  • Closure Properties of CFL
  • Remove Null Production from CFG
    • Recognize all nullable variables -=> Variables producing null directly or indirectly
    • Replace nullable variable by Ι› to find new answers
    • Remove Ι› from a Variable from right hand side
    • If Ι› is part of Language then it can not be removed
  • Remove Unit Production from CFG
    • Unit Production is of the form Ξ± β†’ Ξ², where Ξ±, Ξ² ∈ V
    • Replace the RHS of Ξ± with the RHS of Ξ², if possible
    • Remove all unutilized Ξ± -=> Those which are not reachable from starting

Push-Down Automata

  • FA with Output -=> FA + Stack
  • Number of comparisons of power = 1
  • No choices/guess, Direct answer
  • Properties
    • Number of comparisons = 1
    • No direct answer
    • Power of NPDA > DPDA
  • Push-Down Automata
  • Transition Function
    • If Ο„ and Ο„* are same then no change
    • If Ο„* = Ι› then pop Ο„
    • If Ο„ and Ο„* are different push Ο„
  • PDA Designing
    • Create state diagram
    • Create transitions

Others

  • Ambiguity in CFG - CYK Algorithm
  • Parsing
    • Brute Force
  • Membership Algorithm
    • CYK
  • Machines
    • DPDA
    • NPDA
  • DCFL vs CFL
  • Algorithm
    • Removal of Ξ» Production
    • Removal of Unit
    • Removal of Useless Production
    • Removal of Left Recursion
    • Removal of Left Factoring
  • Normal Form
    • Chomsky
    • Greibeck
  • Simplification of CFG Elimination of Useless symbols
  • Normal forms for CFG: CNF and GNF
  • Pumping Lemma for CFL

Context Sensitive Language (CSL)

  • Number of comparisons = 2
  • Linear Bound Automata (LBA)
    • Turing Machine + limited size tape (Based on input)

REC, RE

  • Recursive Languages
    • Language that is accepted by a halting Turing machine
  • Recursively Enumerable Languages
    • Language that is accepted by a Turing machine -=> Also known as Countably Infinite
  • Turing Machine
    • Read and Write (Update) is allowed
    • Can move in Right & Left direction
  • Turing Machines as acceptor and transducer
  • Multi head and Multi tape Turing Machines
  • Universal Turing Machine
  • The Halting problem
  • Turing-Church thesis
  • Language that is not Recursively Enumerable (RE)
  • Computable functions
  • Chomsky Hierarchy
  • Undecidable problems
  • Post's Correspondence Problem

Closure Properties and Undecidability

Closure Properties Table

  • Closure Property of All

Decidable & Undecidable

  • If algorithm exists for that problem then that problem is decidable
  • Decidable Table
  • Problems
    • Membership Problem
      • A particular String belongs to the Language or not
      • If algorithm exists
    • Finite-Infinite Problem
      • Weather a language is Finite or Infinite
      • Infinite if contains loop
    • Emptiness Problem
      • Weather a language contains nothing
      • Either it does not reach final state or there is not final state
    • Equality Problem
      • Weather two languages of same type is equal -=> Accepting same type of string
    • Ambiguity Algorithm
      • L is Ambiguous
      • A given Grammar is ambiguous if there is a sentence with moe than one derivation tree corresponding to it
    • Completeness Problem
      • Weather the language is contains all possible Strings for input given
    • Intersection Problem
      • Weather the intersection of same type of languages is empty
    • Subset Problem
      • Weather the languages of same types are subset of each other or not
Share: