FOR FREE CONTENT
- Introduction
- String in automata
- Power of Alphabet ( ∑ )
- Introduction of Automata
- Every DFA is NFA
- Design a DFA for Language: “Starting with ‘a’ "
- Design a DFA for Language: “Ending with ‘a’ "
- Design a DFA for Language: “Start with a and end with b”
- Design a DFA for Language: “Not start with ‘a’ or not end with ‘b’ “
- Design a DFA for L = “Start with ‘a’ and end with ‘a’”
- Design a DFA for L = “Start with ‘001’ ”
- Design a DFA for L = “Ending with ‘001’ ”.
- Design a DFA for L = “At least one ‘a’”
- Design a DFA for L = “At most one ‘a’ ”
- Design a DFA for L = “At least two ‘a’ ”
- Design a DFA for L = “Exactly one ‘a’ ”
- Design a DFA for L = “At most two ‘a’ ”
- Design a Machine for L = “Containing substring ‘ab’”.
- Design a Machine for L = “Not containing substring ‘001’ ”
- Difference between DFA and NFA: Minimum number of states
- Design a machine of L = Containing even a where ∑ = {a, b}
- Design a machine of L = Containing odd b where ∑ = {a, b}
- Machine with Unary Alphabet
- Design a machine of L = Even number of a’s AND odd number of b’s
- Design a machine of L = Even number of a’s OR odd number of b’s
- Some exercise problems with same pattern
- Q. UGCNET-July-2018-II-32
- (Number of a) mod 2 = 0 and (Number of b) mod 3 =0
- (Number of a) mod 2 =0 and (Number of b) mod 4 =0
- Design a machine of L= (Number of a) mod 4 <= 2
- Design a machine of L = { ω | |ω|=3}, ∑ = {a, b}
- Solve the related Question
- Design a machine L= {Every substrings of 001}
- Design a machine of L = a* b* where ∑ = {a, b}
- Set of all string no consecutive 1’s where ∑ = {0, 1}
- Design a machine of L = Exactly two a’s where ∑ = {a,b}
- Design a machine of L = At most two a’s where ∑ = {a, b}
- Design a machine of L = Exactly two a’s and two b’s ∑ = {a, b}
- At least two a’s and at least two b’s ∑ = {a, b}
- Design a machine of L = (111)*+ (11111)* , ∑ = {1}
- Design a machine of L = (111+ 11111)* , ∑ = {1}
- NFA to DFA Conversion
- Minimization of DFA
- Null removal or λ move removed
- Some more DFA machine design examples
- Application of DFA and NFA
- How to convert DFA/NFA to Higher Machine
- DFA/NFA to Regular Expression Calculation
- Write a Regular Expression: Example1
- Write Regular Expression: Example2
- Write Regular Expression: Example3
- Example1: find Regular Expression
- Example2: find regular expression
- Find Regular Expression of the given machine
- Example3: Find Regular Expression
- Example4: Find regular expression
- Example5: Find regular expression
- Example6: Find Regular Expression
- Here we calculate Regular Expression
- Q. Select the correct Regular Expression
- Simplification Regular Expressions
- Definition of Mealy and Moore
- Example 1: Machine for Same Input
- Example 2: Machine for 1’s complement
- Example 3: Machine for 2’s complement
- Example 4: Machine for change Sign Bit
- Example 5: Machine for Increment by one
- Example 6: Machine for Full adder
- Example 7: Machine for Mod 3
- How to find minimum no. of state in mod N
- Mealy machine to Moore machine conversion
- Moore machine to Mealy machine conversion
- Power of Language and Machine
- How to identify language
- Example 1: Identification of Language
- Example 2: Identification of Language
- Example 3: Identification of Language
- Example 4: Identification of Language
- Language Identification: Important points
- Language Identify: Examples
- Language Identify: Examples
- Some Exercise and Solve
- Some Exercise and Solve
- Some Examples
- Some More Examples
- Important Exercise and Solutions
- Special Cases: Examples
- Special Cases: Examples
- Special Cases: Examples
- Special Cases: Examples
- Special Cases: Examples
- Special Cases: Examples
- Special Cases: Examples
- Special Cases of CSL: Example
- Important Examples: Identification of language
- Example CSL: Identification of language
- Important Examples: Identification of language
- Important Examples: Identification of language
- Important Examples: Identification of language
- Important Examples: Identification of language
- Important Examples: Identification of language
- Important Examples: Identification of language
- Exercise: Identification of language
- Exercise: Identification of language
- Introduction to Pumping Lemma
- Pumping Lemma Theorem for Regular Language
- Q .UGC-NET 2017
- Example: L= a^n b^n
- Example: L={a^i^2, i≥1}
- Example: L={a^p, p is prime}
- Example: L={a^p, p is not prime}
- Example: L={ωω^R, ωϵ∑*}
- Example: L= Balance parenthesis
- Example: L={ωω, ωϵ∑*}
- Example: L={0^n 1^n, n≥0}
- Example: L={a^n ; n is perfect square}
- Example: L={ω|n_a (ω) = n_b (ω)}, where ∑={a, b}, ω ϵ∑*}
- Exercise
- Shortcut Prove: One Language is Not Regular
- Pumping Lemma Theorem for Context Free Language
- Example: L={a^p ; p is prime}
- Example: L={a^i^2, i≥1}
- Example: L={ωω, ωϵ∑*}
- Exercise
- Ogden’s Lemma for CFL
- Myhill-Nerode Theorem
- Introduction: Push Down Automata
- DPDA and NPDA
- PDA Design Method
- Design PDA of L = a^n b^n
- Design PDA of L = a^m b^n, m<n
- Design PDA of L = a^m b^n, m>n
- Design PDA of L = a^m b^n, m ≤ n
- Design PDA of L = a^m b^n, m ≥ n
- Design PDA of L = a^m b^n, m ≠ n
- Design PDA of L = a^n b^2n
- Design PDA of L = a^2n b^n
- Design PDA of L = n_a (ω) = n_b (ω)
- Design PDA of L = ωω^R
- Subject Mock
Design a machine of the following language:
L = Exactly two a’s and two b’s where ∑ = {a, b}.
Answer:
From the given language it is clear that it is two grade of machine.
Firstly we design a machine for exactly two a’s which same design as exactly two b’s. So, anyone we can design as an example lets design “exactly two a’s”.
.png)
So, as per the given language L = exactly two a’s and two b’s. “exactly two a’s” requires 3 states (we are not considered trap state ), and same as “exactly two b’s” requires 3 states. So, the total grade of states require for L = exactly two a’s and two b’s is 3 x 3 = 9.
We can take a’s state as horizontal direction and b’s state as vertical i.e. three state as horizontal for a and three state as vertical for b.
And apart from 9 states, we require one extra state which identifies trap state for all.
.png)
L = exactly two a’s AND two b’s, so as we know AND means intersection i.e. common states between all states of exactly two a’s and all states of exactly two b’s.
.png)
Minimum NFA = 9 states, Minimum DFA = 10 states (one step for trap state).
If there m a’s and n b’s then
Minimum NFA = (m+1) (n+1) , Minimum DFA = (m + 1) (n + 1) + 1
