String Functions: Prefixes, Suffixes, Substrings

Study Notes

Strings and Their Components

Prefixes: All leading segments of a string. For string "abc", prefixes are ε, a, ab, abc.
Suffixes: All trailing segments of a string. For "abc", suffixes are ε, c, bc, abc.
Substrings: Any contiguous sequence of characters within a string. For "abcd", valid substrings include a, b, c, d, ab, bc, cd, abc, bcd, abcd. Combinations like acd, ac, ad, bd, abd are not substrings.

Language Concepts

Language: A collection of strings formed from an alphabet Σ, denoted by L.
Σ*: Represents all possible strings over an alphabet, including the empty string, constituting an infinite language that encompasses all languages (L ⊆ Σ*).
Finite Language: A specific collection of strings with a limited number. Example: L1 = {aa, ab, ba, bb} over Σ = {a, b}.
Infinite Language: A collection of strings that can grow indefinitely. Example: L2 contains all strings starting with 'a'.
Empty Language: Denoted by Φ (phi) and contains no strings. L = {} is a valid empty language.
Language with Empty String: L = {ε} contains a single empty string but is not an empty language.

Formal Languages

Formal languages consist of statements structured from a defined character set, as seen in programming languages like C'.

ε-NFA (Nondeterministic Finite Automaton with ε-moves)

Definition: An automaton that permits transitions without consuming any input symbol (ε-transitions).
Properties:
- ε-NFAs do not represent a broader class of languages compared to standard NFAs.
- They simplify the design of finite automata while still recognizing the same languages as NFAs.
- Transition function is defined as 𝛿 (q, a) for input symbols and ε.
Structure: Formally defined as M=(Q,∑, 𝛿, q0, F) where:
- Q = set of finite states
- ∑ = set of input symbols
- 𝛿 = transition function from Q × ∑ U { ε } → 2Q
- q0 = initial state
- F = set of final states

Example ε-NFA

Accepts strings comprised of any number of 0's, followed by any number of 1's, followed by any number of 2's, yielding an infinite language.

Deterministic Finite Automaton (DFA)

Language Definition: A DFA can accept strings starting with 'a' over Σ = {a, b}.
Example Language: L includes strings such as a, aa, ab, aaa, etc., showcasing an infinite set.
Transition Diagram:
- q0: Initial state, must transition to q1 upon reading 'a'.
- q1: Final state, accepts any following 'a' or 'b'.
- q2: Dead state for any non-accepted input.

Acceptance of a String in DFA

Given input string w = "abab":
- The transition sequence illustrates movement through states, confirming it reaches final state q1, thereby accepting the string.

These points encapsulate the concepts surrounding strings, languages, and finite automata, providing a framework for further study in formal languages and automata theory.