FOR FREE MATERIALS
- 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
UGC NET 2016
Consider the following identities for regular expressions:
(a) (r + s)* = (s + r)*
(b) (r*)* = r*
(c) (r* s*)* = (r + s)*
Which of the above identities are true?
A. (a) and (b) only
B. (b) and (c) only
C. (c) and (a) only
D. (a), (b) and (c)
Answer:
(a) (r + s)* means set of all strings generated by r and s.
Now (r + s)* = (s + r)* any string constructed by LHS can also be created by RHS and vice versa like λ, r, s, rr, ss, rsrs.
(b) (r*)* = r* again valid as (r*)* = r*. r*. r* i.e. λ, r, rr, rrr, rrrr which is same as r*.
(c) We already see in previous section (See all form of (a + b)*) i.e. (a*b*)* = (a + b)*
If we derive (r* s*)* = (r*s*)(r*s*)(r*s*)...... we will get strings like λ, r, s, rs, rsrs, srsr, rrrr, ssss
And if we derive (r + s)* = (r + s)(r + s)... it will give same strings like λ, r, s, rs, rsrs, srsr, rrrr, ssss.
So, (r* s*)* = (r + s)*
Here a, b, c all are true so, Option D is correct.
