1.

Define Finite Automata

An automaton with finite number of states is called Finite Automata or Finite State Machine.
An automaton will have finite amount of memory.
2. List out applications of FA
Pattern Search
Elevator
Vending Machine
Flip Flops
3. Give regular expression for set of all strings whose length is at least 2 over ∑ = {0,1}
L = {aa, ab, ba, bb, aaa, ……}
= (a+b).(a+b).(a+b)*
4. Describe Decision Properties of CFL
Membership – whether given string is part of the language or not
Emptiness – whether the language is empty or not
Infiniteness – whether the language is infinite or not
5. Define Deterministic Push Down Automata
A deterministic pushdown automaton is a variation of PDA. The class of deterministic
pushdown automata accepts the deterministic CFL, a proper subset of CFL.
6. State properties of regular set
The union of two regular set is regular.
The intersection of two regular set is regular
The complement of a regular set is regular.
The difference of two regular set is regular.
The reversal of a regular set is regular.
The closure of a regular set is regular.
The concatenation of two regular sets is regular.
7. E-Closure with suitable example
The ε closure(P) is a set of states which are reachable from state P on ε-transitions.

8. Name closure Properties of CFL

Union
Concatenation
Kleene Closure
9. Define Deterministic Finite Automata
In DFA, for each input symbol, one can determine the state to which the machine will move.
Hence, it is called Deterministic Automaton. As it has a finite number of states, the machine is
called Deterministic Finite Machine or Deterministic Finite Automaton.
10. Define Non-Deterministic Finite Automata
In NDFA, for a particular input symbol, the machine can move to any combination of the states
in the machine. In other words, the exact state to which the machine moves cannot be
 determined. Hence, it is called Non-deterministic Automaton. As it has finite number of states,
the machine is called Non-deterministic Finite Machine or Non-deterministic Finite Automaton.
11. Define Pushdown Automata
Pushdown Automata is a finite automata with extra memory called stack which helps
Pushdown automata to recognize Context Free Languages. 
12. What is ambiguous grammar? Give an example
A grammar is said to be ambiguous grammar, for deriving a particular string if there exists
more than one LMD or more than one RMD or more than one derivation tree.
1. E → E+E / E-E / id  
From the above grammar String "id + id - id" can be derived in 2 ways:
First Leftmost derivation Second Leftmost derivation
1. E → E + E   E → E - E
2.    → id + E   → E + E - E  
3.    → id + E - E   → id + E - E  
4.    → id + id - E       → id + id - E  
1.    → id + id- id       → id + id - id  
Since there are two leftmost derivation for a single string "id + id - id", the grammar G is
ambiguous.
13. Draw parse tree from the grammar S0B|1A , A0|0S|1AA , B1|1S|0BB to derive the
string 00110101

14. State Regulation expression.

The language accepted by finite automata can be easily described by simple expressions called
Regular Expressions. It is the most effective way to represent any language.
15. What is Kleene star
The Kleene star, ∑*, is a unary operator on a set of symbols or strings, ∑, that gives the infinite
set of all possible strings of all possible lengths over ∑ including λ.
16. State and explain Non-Deterministic Finite Automata(NDFA/NFA) with suitable example
Non-deterministic Automata is a finite automata when there exists many paths for a specific
input from current state to next state and there can be multiple states.
Language L accepts all strings in which third symbol from right end is always ‘a’ over ∑={a,b}

17. Construct NFA transition diagram for transition table as given below
18. What is Push down Automata. Give formal definition of PDA
Pushdown Automata is a finite automata with extra memory called stack which helps
Pushdown automata to recognize Context Free Languages. 
A Pushdown Automata (PDA) can be formally defined as : 
 PDA = (Q, ∑, δ, q0, F, Γ, Z) where
Q is the set of states
∑is the set of input symbols
δ is a transition function which maps Q x {Σ ∪ ∈} x Γ into Q x Γ*.
q0 is the initial state
F is the set of final states
Γ is the set of pushdown symbols (which can be pushed and popped from stack)
Z is the initial pushdown symbol (which is initially present in stack)
19. Construct a PDA that accepts the following languages by final state and empty stack and
write transition functions for that.
L={anbn|n>=1}

20. State Context Free Language?

Context-Free Language (CFL) is a language which is generated by a context-free grammar or
Type 2 grammar and gets accepted by a Pushdown Automata.
Example of CFL accepted by PDA

21. Consider the grammar E+EE|*EE|-EE|x|y. Find leftmost derivation, rightmost

derivation for the string “+*-xyxy” and write parse tree.
22. Construct parse tree for the string “+*-xyxy” from the grammar E+EE|*EE|-EE|x|y.

23. What is Context Free Language?

Context-Free Language (CFL) is a language which is generated by a context-free grammar or
Type 2 grammar and gets accepted by a Pushdown Automata.
Example of CFL accepted by PDA

24. Explain closure properties of Context free language(CFL)

Union: If L1 & L2 are two context free languages, their union L1 ∪ L2 will also be context
free. So CFL are closed under Union. For example, 
L1 = { anbm | m >= 0, n >= 0 } and L2 = { a mbn | n >= 0, m >= 0 } 
L3 = L1 ∪ L2 = { anbm ∪ ambn | n >= 0, m >= 0 } is also context free. 
Concatenation:  If L1 and If L2 are two context free languages, their concatenation L1.L2 will
also be context free. So CFL are closed under Concatenation. For example,  
L1 = { anbn | n >= 0 } and L2 = { c mdm | m >= 0 } 
L3 = L1.L2 = { anbncmdm | m >= 0, n >= 0} is also context free.
Kleene Closure:  If L1 is context free, its Kleene closure L1* will also be context free. So CFL
are closed under Kleene Closure. For example, 
L1 = { anbn | n >= 0 } 
L1* = { anbn | n >= 0 }* is also context free. 
25. Explain Deterministic Finite Automata(DFA) with suitable example
In DFA, for each input symbol, one can determine the state to which the machine will move.
Hence, it is called Deterministic Automaton. As it has a finite number of states, the machine is
 called Deterministic Finite Machine or Deterministic Finite Automaton.
Language L accepts ‘a’ over Σ ={a}

26. Construct DFA which checks whether a given binary number is divisible by 3

27. What is Push down Automata. Give formal definition of PDA

Pushdown Automata is a finite automata with extra memory called stack which helps
Pushdown automata to recognize Context Free Languages. 
A Pushdown Automata (PDA) can be formally defined as : 
 PDA = (Q, ∑, δ, q0, F, Γ, Z) where
Q is the set of states
∑is the set of input symbols
δ is a transition function which maps Q x {Σ ∪ ∈} x Γ into Q x Γ*.
q0 is the initial state
F is the set of final states
Γ is the set of pushdown symbols (which can be pushed and popped from stack)
Z is the initial pushdown symbol (which is initially present in stack)
28. Construct a PDA that accepts the following languages by final state and empty stack and
write transition functions for that.
L={anbn|n>=1}

29. State Context Free Language?

Context-Free Language (CFL) is a language which is generated by a context-free grammar or
Type 2 grammar and gets accepted by a Pushdown Automata.
Example of CFL accepted by PDA
30. Explain Decision properties of Context free language (CFL)
Membership – whether given string is part of the language or not
Emptiness – whether the language is empty or not
Infiniteness – whether the language is infinite or not
31. State and explain NFA with E-transition or E-NFA with suitable example
32. Minimize the following DFA using Table Filling method