Regular Languages and Operations

Operations on Regular Languages are a foundational concept in the Theory of Computation and Automata. These operations allow us to build complex regular languages from simpler ones and understand their closure properties.

🧾 What Are Regular Languages?

Regular languages are languages that can be:

  • Accepted by a Deterministic Finite Automaton (DFA) or Non-Deterministic Finite Automaton (NFA)

  • Described by regular expressions

  • Generated by regular grammars

Regular languages are closed under many operations. This means that if you apply an operation to one or more regular languages, the result is also a regular language.

✅ Major Operations on Regular Languages

1. Union (L₁ ∪ L₂)

  • Definition: The union of two regular languages consists of all strings that are in either L₁ or L₂.

  • Example:
    If L₁ = {a, ab} and L₂ = {b, ba},
    then L₁ ∪ L₂ = {a, ab, b, ba}

  • Regular Expression: a + ab + b + ba

2. Concatenation (L₁ ⋅ L₂ or L₁L₂)

  • Definition: Concatenation includes all strings formed by taking a string from L₁ followed by a string from L₂.

  • Example:
    If L₁ = {a, b} and L₂ = {0, 1},
    then L₁L₂ = {a0, a1, b0, b1}

  • Regular Expression: (a + b)(0 + 1)

3. Kleene Star (L)*

  • Definition: The Kleene star of a language is the set of all strings formed by zero or more concatenations of strings from the language.

  • Example:
    If L = {ab},
    then L* = {ε, ab, abab, ababab, ...}

  • Regular Expression: (ab)*

4. Intersection (L₁ ∩ L₂)

  • Definition: The intersection contains all strings that are present in both L₁ and L₂.

  • Example:
    L₁ = strings over {a, b} ending with a
    L₂ = strings over {a, b} starting with a
    L₁ ∩ L₂ = strings that start and end with a

  • Note: Although regular expressions do not support intersection directly, finite automata can compute it using a product construction.

5. Complement (~L or L')

  • Definition: The complement of a language L includes all strings not in L, over the same alphabet.

  • Example:
    If L = {x ∈ {a, b}* | x ends in a},
    then ~L = strings not ending in a

  • Implementation: Take a DFA for L and swap final and non-final states.

6. Difference (L₁ - L₂)

  • Definition: The difference contains all strings that are in L₁ but not in L₂.

  • Relation: L₁ - L₂ = L₁ ∩ (~L₂)

  • Implementation: Use intersection and complement.

7. Reversal (Lá´¿)

  • Definition: The reversal of a regular language L consists of the reversed versions of all strings in L.

  • Example:
    If L = {ab, aab},
    then Lá´¿ = {ba, baa}

  • Regular Languages are Closed under Reversal

8. Homomorphism and Inverse Homomorphism

  • Homomorphism: Replacing symbols in strings based on a substitution rule.

    • Example:
      Let h(a) = 01, h(b) = 10
      Then h(ab) = 0110

  • Inverse Homomorphism: Given a language L over some alphabet, find the set of strings over another alphabet whose image under the homomorphism is in L.

🧠 Closure Properties Summary

Operation                Closed Under?
Union                        ✅ Yes
Concatenation                    ✅ Yes
Kleene Star                    ✅ Yes
Intersection                    ✅ Yes
Complement                    ✅  Yes
Difference                    ✅ Yes
Reversal                    ✅ Yes
Homomorphism                    ✅ Yes
Inverse Hom.                    ✅ Yes

Comments

Post a Comment

Popular posts from this blog

Theory Of Computation PCCST302 KTU Semester 3 BTech 2024 Scheme

About Me Course Details and Syllabus Module-1 Foundations of Finite Automata Motivation-Computability Need for Mathematical Modelling and automata Introducing automata     on-off switch     coffee vending machine Alphabet, Strings, and Languages Formal Definition of Finite Automata Deterministic Finite Automata - DFA Dead state in DFA Categories of DFA      Category 1: Accept Only the Given Input      Category 2: Starts and ends with      Category 3: Contains substring      Category 4: Specific length     Category 5: Divisibility ( Binary Numbers) Examples  DFA( University Questions) DFA Implementation C Program Non Deterministic Finite Automata - NFA Epsilon NFA  (∈-NFA) Examples NFA( University Questions) Regular Languages Epsilon Closure of NFA Eliminating Epsilon Transitions from NFA Epsilon Free NFA to DFA Conversion - Examples DFA state minimization DFA vs NFA Applications of Fini...
Read more

Non deterministic Finite Automata NFA

Image
  🤖 Formal Definition of NFA An NFA (Nondeterministic Finite Automaton) is a theoretical machine used to recognize regular languages , like a DFA, but it allows multiple transitions for the same input or even no input at all (ε-transitions) . 📘 An NFA is defined as a 5-tuple : M = ( Q , Σ , δ , q 0 , F ) M = (Q, \Sigma, \delta, q_0, F) Where: Symbol Description Q Q A finite set of states Σ \Sigma A finite set called the input alphabet δ \delta The transition function : δ : Q × ( Σ ∪ { ε } ) → 2 Q \delta: Q \times (\Sigma \cup \{\varepsilon\}) \rightarrow 2^Q  (a set of states) q 0 q_0 ​ The initial state , q 0 ∈ Q q_0 \in Q F F The set of accepting states , F ⊆ Q F \subseteq Q 💡 Key Differences from DFA: DFA NFA Only one transition per input                Multiple transitions possible No ε-transitions                ε-transitions allowed Deterministic      ...
Read more

Example DFAs University Questions

Image
 Even number of a's ab as a substring empty set All strings except the empty set over the alphabet {0.1} Accept empty string and 0 every odd position of the string w is 1 begins with 1 ends with 0 {w| w contains at least 3 ones }  {w|w contains the substring 0101 ie; w=x0101y for some x and y} {w|w has length at least 3 and its third symbol is a zero} {w|w starts with 0 and has odd length , or starts with 1 and has even length } construct a DFA which accepts the language L = {a^N | N ≥ 1} String in {a,b} with odd number of a's starting with 01 over the alphabet [1,0} Strings ending with abc Program to build a DFA that checks if a string ends with "01" or "10" build a DFA to accept strings that start and end with same character build DFA that starts and end with 'a' from input (a, b) build a DFA that accepts strings starting and ending with different character DFA of a string starting with 0 and ends with 10? DFA of a string of a's and b's  st...
Read more