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
Context Free Grammar (CFG)
Context Free Grammar
We already discussed definition of CFG at previous chapter (Type of grammar).
General form of Context Free Grammar (CFG):
.png)
Example:
.png)
.png)
There is no left and right context of the left hand of the grammar.
In this above example A → aAb | ab this production has context free because left hand side of the production A has no variable or terminal on left or right side.
Context Free Grammar (CFG) generates Context Free Language (CFL).
Machine of Context Free Grammar (Type 2) is Push Down Automata (PDA).
Now classification of CFG
.png)
