Alphabet, Strings, and Languages

 

🔠 Alphabet, Strings, and Languages

📘 1. Alphabet (Σ)

Definition :

An alphabet is a finite, non-empty set of symbols. It is usually denoted by the Greek letter Σ (sigma).

Examples:

  • Σ = {0, 1} → binary alphabet

  • Σ = {a, b} → common for regular languages

  • Σ = {0, 1, 2, ..., 9} → decimal digits

  • Σ = set of all ASCII characters → for programming languages

📌 Note: The alphabet must be finite. 

Teaching Tip:

Think of the alphabet as the set of building blocks—like letters in a language or keys on a keyboard.

📄 2. String (or Word)

Definition:

A string (or word) over an alphabet Σ is a finite sequence of symbols chosen from Σ.

  • If Σ = {a, b}, then:

    • a, ab, bba, aaabb are all strings over Σ.

    • The string xyz is not a string over Σ.

Special Case – Empty String (ε):

  • The empty string, denoted ε, is the string with zero symbols.

  • It is not the same as a string containing a space or "null".

  • Every alphabet has ε as a valid string.

Operations on Strings:

  • Concatenation: Combining two strings
    If x = ab and y = ba, then xy = abba

  • Length: Denoted |w| for a string w
    If w = aba, then |w| = 3, and |ε| = 0

🌐 3. Language

Definition:
A language is a set of strings formed from an alphabet Σ.

  • So:
    A language is a subset of Σ*
    (Where Σ* is the set of all possible finite-length strings over Σ)

Examples:

  • Σ = {0, 1}

    • L = {ε, 0, 1, 00, 11} → A finite language

    • L = {w ∈ Σ* | w has even number of 0s} → An infinite language

  • Σ = {a, b}

    • L = {a^nb^n | n ≥ 0} → L = {ε, ab, aabb, aaabbb, ...}

Common Notations:

  • Σ*: Set of all strings over Σ (including ε)

  • Σ⁺: Set of all non-empty strings over Σ
    (i.e., Σ⁺ = Σ* − {ε})

🔁 4. Key Theoretical Properties 

  • Languages are the input/output for automata.

  • We classify languages based on complexity and recognizability:

    • Regular languages (finite automata)

    • Context-free languages (pushdown automata)

    • Recursively enumerable (Turing machines)

  • Every string belongs to exactly one of: a language or its complement (Σ* − L)

🎓 Summary:

Term       Description      Example (Σ = {a, b})
    Alphabet                        Finite set of symbol            {a, b}
    String                        Finite sequence from Σ             abba, ε
    Σ*                        All strings over Σ            ε, a, b, aa, ab...
    Language                        Subset of Σ*            {ab, ba, aab}


Understanding alphabet, strings, and languages is essential before moving to:

  • Regular expressions and finite automata

  • Grammar derivations

  • Decidability and Turing machines

They form the foundation of all theoretical models of computation.

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 Theory of Computation PCCST302 Model Question Paper and Answers 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 -...
Read more

Formal Definition - Turing Machine

Image
  📘 Formal Definition - Turing Machine A Turing Machine is a nine-tuple M = ( Q , Σ , Γ , δ , B , ⊢ , s,t, r) M = (Q, \Sigma, \Gamma, \delta, s_0, B, ⊢, s_{acc}, s_{rej}) where: Q – a finite set of states (typically denoted r , s , t , ... ). Σ – the input alphabet , which does not contain the blank symbol B or the left-end marker ⊢ . Γ – the tape alphabet , satisfying Σ ⊆ Γ , B ∈ Γ , ⊢ ∈ Γ Σ ⊆ Γ, \quad B ∈ Γ, \quad ⊢ ∈ Γ Every cell of the tape contains one symbol from Γ. δ – the transition function δ : ( Q − { t,r } ) × Γ → Q × Γ × { L , R } δ : (Q - \{s_{acc}, s_{rej}\}) \times Γ \to Q \times Γ \times \{L, R\} Given the current state and the symbol under the tape head, the machine writes a symbol, moves Left (L) or Right (R), and enters a new state. s ∈ Q – the initial (start) state . B ∈ Γ – the blank symbol , representing the empty tape cell. ⊢ ∈ Γ – the left-end marker , which appears at the extreme left of the tape and is never overwritte...
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