Scribd
Upload
54 views10 pages

Applications and Limitations of Finite Automata

The document contains questions related to finite automata, formal languages, regular grammars, context-free languages, and pushdown automata. It includes questions ranging from 2 marks to 12 marks covering topics like distinguishing between NFA and DFA, applications of Mealy and Moore machines, minimization of finite automata, closure properties of language classes, pumping lemma, ambiguity in context-free grammars, normalization of grammars, and conversion between PDAs and CFGs.

Uploaded by

Gurjit Singh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
54 views10 pages

Applications and Limitations of Finite Automata

The document contains questions related to finite automata, formal languages, regular grammars, context-free languages, and pushdown automata. It includes questions ranging from 2 marks to 12 marks covering topics like distinguishing between NFA and DFA, applications of Mealy and Moore machines, minimization of finite automata, closure properties of language classes, pumping lemma, ambiguity in context-free grammars, normalization of grammars, and conversion between PDAs and CFGs.

Uploaded by

Gurjit Singh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Finite Automata

2 Marks question
1. Distinguish between NFA and DFA.
2. Distinguish between Mealy and Moore Machines.
3. Applications of Mealy and Moore machines.
4. Applications and limitations of finite automata.
5. Discuss the different properties of transition function.
6. Determine the language generated by grammar having productions:
S→aS|A, A→bB|b, B→dC|˄, C→˄
7. Construct a DFA for the language over {0, 1}* such that it contains “000” as a substring.
8. Write RE for the languages of all Strings that do not end with 01.
9. Compare FA, NFA and NFA-^.

4 Marks question
1. Design a DFA with minimum number of states that recognizes the set of all binary strings
which contains four consecutive 1’s and give the formal description of the designed DFA.

2. Design a DFA equivalent to M=({q0 , q1 , q2}, {1, 0} , δ, q0 , {q2}) where the state diagram
for δ is given below: (4)

3. Construct deterministic finite automata to recognize odd number of 1’s and even number
of 0’s.
4. Design DFA to accept strings over ∑ = (0,1) with two consecutive 0’s.
5. Construct a Non-deterministic finite automata to accept strings containing the substring
0101.
6. Construct a DFA for the following: (a) All strings that contain exactly 4 zeros. (b) All
strings that don’t contain the substring 110.
7. Define regular expression. Prove that following regular expressions are equivalent.
a*(ab)*(a*(ab)*)* = (a+ab)*
10. Construct deterministic finite automata to recognize odd number of 1’s and even number of 0’s?
11. Convert the NFA given in Table below to its corresponding DFA and draw the DFA.

12. Convert the Mealy machine shown in given figure into Moore machine.

13. Figure shows NFA-^. Draw an FA accepting the same language.

12 Marks question
1. What do you mean by minimization of finite state automata? Construct a minimum state
automata equivalent to a automata given below:

2. What do you mean by equivalence of states in a Finite Automata? Construct a minimum


state automaton equivalent to Finite Automata with transition table given below: (12)
States Input
0 1
→A B F
B A F
C G A
D H B
E A G
F H C
G A D
H A C

3. Construct a minimized DFA for the regular expression 10+(0+11)0*1


4. Construct a minimized DFA for the regular expression 1. (01 + 10)* + 0. (11 + 10)*.
5. Compare the Mealy and Moore machine? Define the characteristics of each. Transform
the following Mealy machine into Moore machine:

Present Next State


State
Input=0 Input=1
State Output State Output
q1 q3 0 q2 0

q2 q1 1 q4 0

q3 q2 1 q1 1

q4 q4 1 q3 1

Formal Languages
2 Marks question
1. Identify the languages generated by the following grammars.
a) S -> 0S1 | 0A1 A-> 1A | 1
b) S -> 0S1 | 0A1 A -> 1A0 | 10
2. Construct the grammar representing the set of palindromes over (0+1)*
4 Marks question
1. Prove that each of the classes of languages is closed under union operation.

12 Marks question
1. What are the different types of languages as per Chomsky classification? Describe each
class in detail with the help of examples. Also prove that each class is closed under the
union, concatenation and transpose operation.

Regular Grammar
2 Marks question
1. Applications of regular expressions.
2. What do you mean by null production and unit production? Give an example.
3. Give a regular expression for the set of all strings having odd number of 1’s.
4. Give the regular expression for the set of all strings ending in 00.
5.

4 Marks question
1. Show that L = { ww | w € { a,b }* } is not regular using pumping lemma.
2. Construct a DFA with reduced states equivalent to the regular expression 10+(0+11)0*1
3. Prove that P + PQ* = a* bQ* where, P = b + aa*b and Q is regular expression.
4. Prove the following identity:
(a*ab + ba)* a* = (a + ab + ba)*
5. Find the regular expression corresponding to the given automata:
6. Construct an equivalent FA for the given regular expression (0+1)*(00+11)(0+1)*
7. Prove R=Q+RP has unique solution, R=QP*
8. Is regular set is closed under complementation? Justify.
9. Construct a grammar for set of strings that contain equal number of a’s and b’s over ∑ =
{a,b}
10. Construct the grammar representing the set of palindromes over (0+1)*
11. Derive the regular expression for the finite automata represented by following transition
diagram:

12. State Kleens Theorem. Construct the deterministic finite automaton equivalent to the
regular expression: ( a b ¿ ) (a+b)¿ ( b+ab)
13. Derive the regular expression for the following Transition Diagram

12 Marks question
Context Free Language
2 Marks question
1. Consider G whose productions are S-> S + S | S * S , S-> b | a. Show that S can derive
a*b+a*b and construct a derivation tree whose yield is a*b+a*b
2. Show that the grammar S-> aB | ab , A-> aAB | a , B-> ABb|b is ambiguous.
3. Remove the unit production from the grammar S->AB,A->E,B->C,C->D,D->b,E->a.
4. What are the type of productions in Griebach normal form?

5.

4 Marks question
1. Explain Greibach normal form in detail.
2. Construct a grammar in Greibach normal form equivalent to the grammar
S->AA , A-> SS | b.
3. Convert the grammar S-> AB, A-> BS | b, B-> SA | a into GNF.
4. Reduce the following CFG to GNF:
S-> ABb | a, A-> aaA, B-> bAb
5. What do you mean by ambiguity in context free grammars.
Show that a CFG G with productions S->SS | (S) | ^ is ambiguous.
6. Consider the following productions:
S-> aB | bA
A -> aS | bAA | a
B-> bS | aBB | b
For the string aaabbabbba, find
a) the leftmost derivation,
b) the rightmost derivation, and
c) the parse tree

7. Show that L = { ap | p is as prime} is not context free language using pumping lemma
8. Show that {anbncn | n>0} is not a context free language using the pumping lemma.
9. Explain the different steps for simplification of context free grammar. Take an example
grammar and simply it by applying the different steps for this process
10. Convert the following grammar G in greibach normal form.
S→ABb|a A→aaA|B B→bAb
11. Construct a derivation tree for the string 0011000 using the grammar S->A0S |0 | SS , A-
> S1A | 10.
12. State and prove pumping lemma for CFL
13. Reduce the following grammar into Chomsky Normal form:
S→ab|aSC|BA,A→a|Cb|bb,B→aB|∈
14. Consider following grammar:

S -> ASB | Λ
A -> aAS | a
B -> SbS | A | bb
i. Eliminate useless symbols, if any.
ii. Eliminate Λ productions

12 Marks question
1. What is the purpose of normalization? Construct the CNF and
GNF for the following grammar and explain the steps.
S→aAa | bBb |€
A→C|a
B→C|b
C→CDE | €
D→A|B|ab

2. What you do mean by simplification of context free


grammar? How a grammar can be simplified? Find the
reduced grammar equivalent to the given grammar G, whose
productions are given below:
S → bA|aB , A → bAA|aS|a∨C , B → aBB|bs∨b , D → c

Push Down Automata


2 Marks question
1. PDA is more powerful than a finite automaton. Justify this statement.
4 Marks question
1. Convert the grammar S-> aSb | A, A-> bSa | S | ^ to a PDA that accepts the same
language by empty stack.
2. Construct a Push Down Automata accepting {anb2n ǀ n≥1} by empty stack.
3. Construct a Push Down Automata accepting {ambn ǀ m>n≥1} by empty stack.

4. What is Push Down Automata? How is it different from a Finite Automata? Discuss the
acceptance of a string by Push Down Automata with the help of suitable examples.

5. What are the different ways of language acceptances by a PDA and define them?
6. Compare Deterministic and Non deterministic PDA. Is it true that non deterministic PDA
is more powerful than that of deterministic PDA? Justify your answer.
7. Prove that if there exists a PDA that accepts by final state then there exists an equivalent
PDA that accepts by Null state.
8. Construct an equivalent PDA for the following CFG
S->aAB | bBA
A->bS | a
B->aS | b
9. Convert the following PDA into an equivalent CFG.
δ (q0,a0,z0)->(q1,z1z0)
δ(q0,b,z0)->(q1,z2z0)
δ(q1,a,z1)->(q1, z1z1)
δ(q1,b,z1)->(q1, λ)
δ(q1,b,z2)->(q1,z2z2)
δ(q1,a,z2)->(q1, λ)
δ(q1, λ,z2)->(q1, λ) // accepted by the empty stack

12 Marks question
1. What is Push Down Automata? How is it different from a Finite Automata? Discuss the
acceptance of a string by Push Down Automata with the help of suitable examples.
2. Construct a Push Down Automata accepting {anbman ǀ m,n≥1} by empty stack. Construct
the corresponding context free grammar accepting the same set.

3. What is Push Down Automata? How is it different from a Finite Automata? Discuss the
acceptance of a string by Push Down Automata with the help of suitable examples.
4. Construct a Push Down Automata accepting {anbman ǀ m,n≥1} by null store. Construct
the corresponding context free grammar accepting the same set.

Turing Machine, Context Sensitive Language

2 Marks question
1. What are the applications of Turing Machine?
2. State and prove the Post’s correspondence problem.
3. Discuss relation between LBA and CSL.
4. Define turing machine

4 Marks question
1. What is the purpose of a Turing Machine? Discuss Turing Machine in detail and also the
acceptability of strings by Turing Machine.

2. What are context sensitive languages? Discuss context sensitive languages in detail.

3. Design a Turing machine with no more than three states that accepts the language
a(a+b)*. Assume ∑ = {a,b}
4. What are the differences between a Finite automata and a Turing machine?
5. Explain the different models of Turing machines.
6. What is recursively enumerable language?
7. State when a problem is said to be decidable and give an example of an undecidable
problem.
8. What are context sensitive languages? Discuss context sensitive languages in detail.

9.

12 Marks question
1. Discuss the steps to design a Turing Machine. Design a Turing Machine that accepts the
language: L={1n2n3n|n≥1} (12)

2. Construct a Turing machine that recognizes the language L={anbn , n>1}. Show an ID for
the string ‘aabb’ with tape symbols.
3. How Turing machine is important in finding computation to different problems. Design a
Turing Machine to recognize all strings having an odd number of 1’s over {0,1}. Give the
Trace or Instantaneous description for w=0011010
4. Design the Turing machine to recognize the language: {an bn cn | n >=1}.
5. Design a PDA, M to accept L = { an b2n | n ≥ 1 }.
6. Define Push Down Automata (PDA). Design and draw a deterministic PDA
accepting strings with more a’s than b’s. Trace it for the string “abbabaa”.

Common questions

Powered by AI

Context-sensitive languages require grammar rules where the left side can be a longer string, unlike single non-terminals in context-free grammars . They capture more complex constructs, such as L = { anbncn | n>0 }, and are used in scenarios requiring precise syntax rules. Context-free languages efficiently model nested structures like balanced parentheses but can't express certain core constraints met by context-sensitive languages .

Minimization of finite state automata reduces the number of states to simplify design without altering language recognition . The general steps include: identifying and merging equivalent states using equivalence classes, removing redundant states, and ensuring reduced automaton is deterministic . This process improves efficiency and resources usage in implementations .

PDAs are more powerful than finite automata as they can recognize a broader class of languages, particularly context-free languages, due to their stack-based memory . Finite automata can only recognize regular languages because they lack memory to handle nested structures . However, PDAs are still limited compared to Turing machines in terms of non-deterministic processes and processing capability .

Transitioning between a Mealy and Moore machine involves adjusting outputs to be associated with states in a Moore setup or states-and-transitions in a Mealy one . This transformation might be necessary when system requirements dictate a change in how outputs are generated, influencing design complexity and latency. Moore machines simplify hardware implementation while Mealy machines optimize responsiveness .

The Mealy machine outputs depend on the input and current state, while the Moore machine's outputs depend solely on the current state . Mealy machines can be more responsive since outputs can change with inputs. Moore machines are simpler with predictable state-driven outputs. Mealy machines are preferred in situations requiring immediate response to inputs, whereas Moore machines suit applications needing stable outputs .

The pumping lemma asserts if a language is regular, any sufficiently long string in it can be split into xyz such that for any repeat of y, the string remains in the language . By finding a string violating this, one can prove the language isn't regular. For L = { ww | w ∈ {a,b}* }, assume it’s regular, use the lemma for contradiction by showing repeats of a midpoint string fail .

Finite automata are used in various applications such as text processing, compilers, and network protocols due to their ability to model simple sequential logic . However, they are limited by their inability to handle problems requiring context-sensitive recognition or infinite memory, as finite automata have a finite number of states .

The main difference between NFA and DFA is the way in which transitions are handled. In a DFA, for a given state and input character, there is exactly one possible next state . In contrast, an NFA can have multiple next states for the same input character, or none at all . Additionally, an NFA can include epsilon transitions (transitions without input), which DFAs cannot .

To construct a DFA to recognize binary strings containing '000', create states representing the number of consecutive '0's encountered. Start at q0; transition to q1 with '0', to q2 with '00', and to q3 with '000', which is an accept state. Any non-'0' input moves back to q0. The formal description includes: states {q0, q1, q2, q3}, alphabet {0, 1}, transition function δ, start state q0, and accept state q3 .

A Turing Machine extends a finite automaton with an infinite tape for memory, making it capable of performing any computation that can be described algorithmically, thus recognizing a broader class of languages, including recursively enumerable ones . Finite automata, contrasted, lack the capacity to process beyond regular languages, limited by finite states without additional memory . As such, Turing Machines models computable problems, acting as a theoretical baseline for computational complexity .

You might also like