Hey Guys welcome to thetechxplosion, today we are going to learn Deterministic finite automata(DFA). And we will cover all the points related to this type of automata which help you in competitive exams, or university exams.
Automata
Automata is a machine that we used in the representation of finite and infinite languages. In other words, Automata is an abstract model that actually checks whether the language is acceptable or not.
Deterministic Finite Automata
what does a deterministic word mean? It means that if we have a state suppose ‘q0’ and let’s apply an alphabet on it ‘a’. Then ‘a’ will move to a particular state ‘q1’ and you can also name the states. So in the case of DFA, there is a fixed state where a single alphabet will move. DFA is denoted with 5 symbols given below.
- Q: It is a set of all final states or it is the collection of all the possible states in the representation.
- ∑ : is a finite set of symbols, called the alphabet of the automaton or (a,b)
- δ: It is the transition function. It means the transition of an alphabet from one state to another state.
- q0: It is the initial state or starting state from where any input is processed [q0 ∈ Q].
- F: is a set of all final state/states of Q where F ⊆ Q.
So let us discuss deterministic automata with examples, suppose we need to write a language in which strings start with the letter ‘a’. let’s write from a minimum string:
{a, aa, aaa, ab, abb, abab,…….} <- it is the part of the infinite language. So we need to represent this language in the form of deterministic finite automata. Let us start with the designing part. Suppose we take an initial state which is generally denoted as ‘q0’.
WANNA KNOW : AN INTRODUCTION TO HTML S TAG
Step 1: Design minimum to minimum language representation with a single alphabet ‘a’
->q0–a–>q1
here, alphabet ‘a’ moves to q1 and the let q1 be the final state, because in DFA there is only a fixed final state which accepts ‘a’.
Step 2: Remaining representation
if you think, the language representation in the first step is DFA. then you are wrong because we have another alphabet that is ‘b’.
In the above update figure from step 1 is a Deterministic finite Automato for infinite language. Simple, alphabet ‘a’ starts from q0 to final state q1. There is another state under the q0 which is called trap state. Alphabet ‘b’ has trapped from q0 because we need to represent the language starting always with only a. And q1 also has two alphabets a and b. So make the self-loop on it because there is no ending string condition in the question. So this is all about deterministic automata.
Alphabet: An alphabet is a finite set of symbols which is denoted as ‘∑’ or sigma
For Example: ∑ = {a, b, c, d, e} is an alphabet set where ‘a’, ‘b’, ‘c’, ‘d’, & ‘e’ are the symbols.
String
A string in automata is defined as a finite sequence of symbols that is taken from sigma ∑.
For Example : ‘cabcd’ is a valid string on the alphabet set ∑ = {a, b, c, d}
Length of a String
Definition − It is the no. of symbols present in a string and it is denoted by a symbol |S|.
Examples −
If the S = ‘cabcadc’, So the string length or |S| will be 7.
If |S|= 0, it is called an empty string that is denoted by lambda λ or ε
Kleene Star
Definition − The Kleene star is denoted as ∑*, it is a unary operator on a set of strings or symbols. ∑, that gives the infinite set of all successful strings with possible lengths over ∑ including lambda λ.
Representation of Kleene star: ∑* = ∑0 ∪ ∑1 ∪ ∑2 ∪………, where the ∑p is the set of all possible strings of length ‘p’.
For Example: If ∑ = {a, b} then ∑* = {λ, a, b, aa, ab, ba, bb, and so on}
Kleene Closure / Plus
Definition: It is the infinite set of all possible strings of all possible lengths over ∑ excluding λ and it is denoted by giving a plus sign after sigma ∑+
Representation of Kleene plus − ∑+ = ∑1 ∪ ∑2 ∪ ∑3 ∪…….
Expression: ∑+ = ∑* − { λ }
For Example: If the alphabet ∑ = { a, b } so the ∑+ will be written as { a, b, aa, ab, ba, bb,………..}
- 7 Rules of Successful Students: Effective Hacks to Give a Try Today
- Are Collaboration Solutions Professionals in Demand? Become One with Cisco CCNP Collaboration Certification
- Tax Preparation Tips
- What is a bad reputation score in my life? What Are They and Why Are They Important?
- What Are Some Rewarding Careers in Rehabilitation?
Leave a Reply