Scribd
Upload
4 views4 pages

Mod1 Half

The document defines key concepts in formal language theory, including language, strings, alphabets, and the power of an alphabet. It explains deterministic finite automata (DFA) and nondeterministic finite automata (NFA), detailing their structures, functions, and examples. DFAs have unique next states for each input, while NFAs can have multiple possible next states and ε-transitions.

Uploaded by

ksamrutha06
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views4 pages

Mod1 Half

The document defines key concepts in formal language theory, including language, strings, alphabets, and the power of an alphabet. It explains deterministic finite automata (DFA) and nondeterministic finite automata (NFA), detailing their structures, functions, and examples. DFAs have unique next states for each input, while NFAs can have multiple possible next states and ε-transitions.

Uploaded by

ksamrutha06
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

1.

Language

A language is a set of strings formed using symbols from a given alphabet.

Example:

2. String

A string is simply a sequence of symbols taken from a given alphabet.

Example: (using the binary alphabet {0, 1}):

• "01101" is a string
• "1" is also a string

3. Power of an Alphabet

The power of an alphabet refers to all possible strings that can be formed using the symbols
of the alphabet with a specific length.
4. Alphabet

An alphabet is a finite, non-empty set of symbols.

• Example:

5. Reverse of a String

The reverse of a string is the string written backwards.

If w = a₁a₂…aₙ, then wᴿ = aₙ…a₂a₁.

• Example:
If w = "abcde", then wᴿ = "edcba".

Determinism:

• DFA (Deterministic Finite Automata)

• Each input has exactly one unique next state

• No guessing or multiple choices

• Simple and easy to design

• Faster to simulate (one path only)

Deterministic Finite Automaton (DFA)


A DFA is a finite automaton where for each state and input symbol, there is exactly one
next state.
It is completely deterministic, meaning there is no ambiguity in transitions.
Formally defined as a 5-tuple:

DFA = (Q, Σ, δ, q₀, F)


where,

1. Q = finite set of states


2. Σ = finite set of symbols (alphabet)
3. δ = transition function δ: Q × Σ → Q
4. q₀ ∈ Q = start state
5. F ⊆ Q = set of final/accepting states

Example DFA (accepts all strings ending with ‘01’):

• Q = {q₀, q₁, q₂}


• Σ = {0,1}
• q₀ = start state
• F = {q₂}
• δ defined as:

• δ(q₀,0) = q₁, δ(q₀,1) = q₀


• δ(q₁,0) = q₁, δ(q₁,1) = q₂
• δ(q₂,0) = q₁, δ(q₂,1) = q₀

Nondeterministic Finite Automaton (NFA)

An NFA is a finite automaton where for a given state and input symbol, there may be
multiple possible next states (or none at all).
NFAs can also have ε-transitions (move without consuming input).
An input is accepted if at least one possible path leads to a final state.

Formally defined as a 5-tuple:

NFA = (Q, Σ, δ, q₀, F)


where,

1. Q = finite set of states


2. Σ = finite set of symbols (alphabet)
3. δ = transition function from a state & input symbol, it may go to a set of
states.
4. q₀ ∈ Q = start state
5. F ⊆ Q = set of final/accepting states

Example NFA (accepts strings ending with ‘01’):

• Q = {q₀, q₁, q₂}


• Σ = {0,1}
• q₀ = start state
• F = {q₂}
• δ defined as:

▪ δ(q₀,0) = {q₀, q₁}, δ(q₀,1) = {q₀}


▪ δ(q₁,1) = {q₂}
▪ δ(q₂,0) = ∅, δ(q₂,1) = ∅

You might also like