Theory of Computation Study Notes

Theory of Computation - CSE1008

• Instructor: Dr. Manomita Chakraborty
• Affiliation: SCOPE, VIT-AP University, Amaravati, AP, India
• Date: 3/10/2026

MODULE 3 & 4

• Coverage of closure properties for regular languages, decision properties, and applications of regular grammar.

Closure Properties for Regular Languages

• Definition: A closure property is a characteristic of a class of languages such that applying specific operations (union, intersection, etc.) to languages within that class results in a language that remains within the same class.

Closure Properties

1. Union Operation:

   • For languages L and M represented by regular expressions R and S, respectively,
   • The resulting regular expression is $R + S$, which denotes the language L igcup M.
   • Example: If L = {0, 1} and M = {10, 11}, then R + S = {0, 1, 10, 11}.

2. Intersection:

   • Given languages L and M, the regular expression for their intersection can be represented as:
   • R ext{ for } L igcap M.

3. Complement:

   • The complement of a language L over an alphabet Σ is defined as $Σ^* - L$.
   • Since $Σ^*$ is regular, the complement of a regular language is always regular.

4. Kleen Closure:

   • For any regular expression R, $R^*$ defines a language that can be formed by concatenating strings in L zero or more times.

5. Positive Closure:

   • For a language L, $R^+$ is a regular expression denoting one or more concatenations of strings in L.

6. Reverse Operator:

   • Given a language L, $L^R$ defines the set of strings whose reversal is in L.
   • Example: If L = {0, 01, 100}, then $L^R = ext{{0, 10, 001}}$.

7. Set Difference Operator:

   • If L and M are regular languages, then $L - M$ represents the set of strings in L but not in M.

8. Homomorphism:

   • A mapping that substitutes each symbol of an input language with a string, resulting in another language that is also regular.
   • Example: If $H(a) = 001$ and $H(b) = 11$, and given L = {aa, bab}, then $H(L) = ext{{001001, 1100111}}$.
   • If L is regular and H is a homomorphism, then $H(L)$ is regular.

9. Inverse Homomorphism:

   • The process of mapping elements of a homomorphic language back to the original. If L is regular, then its inverse homomorphism H^{-1}(L) is also regular.
   • Example: If $H(a) = 0$, $H(b) = 1$, and $H(c) = 01$, taking L = {0011001}, we get $H^{-1}(L) = ext{{aabbaab, aabbac, acbaab, acbac}}$.

Decision Properties for Regular Languages

• Definition: A decision property is characterized by algorithms that determine whether certain conditions hold for formal language structures, such as Deterministic Finite Automata (DFA).

• Bibliography: Review sections 4.2 and 4.3 from "Automata Theory, Languages, and Computation" by John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman.

Applications of Regular Grammar

• Use cases for regular grammar include:
  1. Lexical analyzers in compilers
  2. Text searching
  3. Pattern matching (like regex)
  4. Finite state machines in digital design
• Regular grammars need to be in standard forms:
  • Right Linear
  • Left Linear

Right Linear Grammar

• In right linear grammar, non-terminals appear on the rightmost side of the production:
  • Syntax: A ⇢ a | aB | ε
  • Example Productions:
    • $S <br /> ightarrow 00B | 11S$
    • $B <br /> ightarrow 0B | 1B | 0 | 1$

Left Linear Grammar

• In left linear grammar, non-terminals exist at the leftmost side of the production:
  • Syntax: A ⇢ a | Ba | ε
  • Example Productions:
    • $S <br /> ightarrow B00 | S11$
    • $B <br /> ightarrow B0 | B1 | 0 | 1$

Finite Automata to Right Linear Grammar

• Steps to convert:
  1. Define states on input 'a': $A <br /> ightarrow aB$
  2. Define states on input 'b': $A <br /> ightarrow bC$
  3. Continue similar definitions for B and C.
  4. Add final state transitions accordingly.

Finite Automata to Left Linear Grammar

• Steps involve:
  1. Reverse the finite automata.
  2. Write in right linear grammar format.
  3. Reverse the right linear grammar to obtain left linear grammar.

Context-Free Grammar (CFG)

• Definition: A CFG is represented as a quadruple (V, T, P, S) where:
  • V: Set of non-terminal symbols
  • T: Set of terminal symbols where V ∩ T = ∅
  • P: Finite set of production rules of the form A → α
  • S: The start symbol

Example CFGs

1.** CFG for language {a, b, c}:**

• $P: A → aA | abc$

1. CFG for nested structures:
   • $P: S → aSa | bSb | ε$

Context-Free Languages

• Definition: CFGs define context-free languages (CFLs).
• If $G = (V, T, P, S)$ is a CFG, then $L(G) = ext{{s | S ⇒ s}}$ is the language of G.
• Properties:
  • CFGs are powerful in representing nested structures.
  • Some languages, like {0^n1^n | n ≥ 0}, are CFL yet not regular.

Applications of Context-Free Languages

• Used in compiler parsing, markup languages (like HTML/XML), and syntactic checking for programming constructs.

Derivations in Context-Free Grammars

• Derivation Definition: The process of replacing variables in a string with the right side of production rules to produce strings purely composed of terminals.
• Examples of derivation sequences and parse trees are provided for various context-free languages.

Ambiguity in Context-Free Grammars

• A context-free grammar is ambiguous if a string can have more than one valid derivation tree.
• Discussion includes methods to remove ambiguity, such as left factoring and precedence rules.