- 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

__Solution:__

It is simple here only one comparison is present because **‘ab’** and **‘cd’**** **both are treated as single symbols like **a** and **b**.

So, one comparison and push, pop is cleared.

Push all **‘ab’**** **on the stack and whenever we get **‘cd’**** **pop **‘ab’**** **from the stack. If the stack is empty (number of **‘ab’**** **equals to the number of **‘cd’**** **then the string is accepted.

** **

There is no comparison is present in this language because n and m are independent. Only infinite order is present.

We already solve this type of problem earlier. Here one comparison is present and push, pop is cleared also.

Here the power of first **‘****a****’** is the sum of the power of **‘****b****’** and next** ‘****a****’**. Push all first **a’s**** **on the stack. When we get **‘****b****’** pop **a’s**** **which is on the stack and the same way when we get next **‘****a****’ **in input pop **‘****a****’ **which is on top of the stack.

If the stack is empty i.e. number of first **‘****a****’ **is equal to the number of **‘****b****’ + **number second **a’s****, **then the string is accepted.

** **

If we see carefully it has two infinite comparisons at a time,

And

Because there is at a time two infinite comparison we cannot solve it by stack (Stack only works with at a time one comparison which follows LIFO order).

**So, it is not Context-Free Language (CFL)**.

** **

**Note:**** Actually ****DCFL**** is less power than ****NCFL**** (****DCFL < NCFL****). So, we consider ****CFL**** as ****NCFL**** sometimes because it is of the highest power of ****CFL****.**

It is almost the same as the above example.

It has two infinite comparisons at a time,

And

As we know at a time two comparison is only done by **Context-Sensitive Language (CSL).**

Generally, we think in this language one comparison is present. The first number of **‘a’** with the second number of **‘a’**. But it is not true **same symbol not require to compare with the same symbol**.

It is almost the same above language because **‘ab’** is treated as a **single symbol **just like **‘a’** in the above example.

So, as we know there is **no requirement to compare with the same symbol**.