REVA UNIVERSITY

School of Computer Science and Engineering

QUESTION BANK

Academic year : Odd Sem 2020 - 21

Sub name : Finite Automata and Formal Sub-code : B19CS5010 Sem & Sec: 5 & F
Languages

UNIT-1
Q. Blooms Course
Questions
No. Taxonomy Outcomes
level Mapped
1 1
Define with an example (i) Alphabet (ii) Power of an alphabet (iii)
1
Concatenation (iv) Language

2 Contrast the difference between transition function and extended 2

transition function. Draw a DFSM for the language L= {wabw|w ε
1
{a,b}*}. With extended transition function, state whether the string
‘abab’ is Accepted/Rejected.
3 Draw a DFA to accept the strings of a’s and b’s (i) ending with bab (ii) 1
1
start with ‘a’ and end with ‘b’
4 Define DFSM. Draw a DFSM to accept decimal strings divisible by 3. 1 1
5 Deterministic Finite Automata can be formally defined using 5 tuples, 1
Define all those 5 tuples and Model a Deterministic finite automaton in
such a way that it should accept the strings of 0's and 1's which starts 1
with 01 and ends with 11.

6 Obtain the NFA to accept strings of a's and b's ending with bba and 1
convert the same into DFA. 1

7 Any number interpreted as a Decimal integer which is divisible by 3 can 1

be valid strings in the language. Obtain a DFA which accepts set of all
1
strings which are divisible by 3.

8 Define the formal definition of DFA, and also design a DFA to accept 1
strings of a’s and b’s ending with ab or ba. Trace the string by
considering the example: aab and abb, show that the string is accepted 1
or rejected.

9 Classify the differences between Deterministic finite automata, Non- 2

1
Deterministic finite automata and Ԑ-NFA. Give an example for each.
10 Observe the string 01112. Model a deterministic finite automata that 1
accepts the strings of 0’s, 1’s and 2’s begin with ‘0’ followed by odd
1
number of 1’s and ending with ‘2’. Name any four applications of finite
automata.
11 Any number interpreted as a binary integer which is divisible by 5 can 1 1
 be valid strings in the language. Obtain a DFA which accepts set of all
strings which is divisible by 5.
12 Practically NFA and Ԑ-NFA cannot exist. For this we need to convert 1
all NFA and Ԑ-NFA into DFA. Convert the following Ԑ-NFA into
equivalent DFA.
∂ Ԑ a b c 1
→p Ф {p} {q} {r}
q {p} {q} {r} Ф
*r {q} {r} Ф {p}
13 Apply subset construction method and convert the following NFA to 1
DFA.
∂ 0 1
→q0 q0 {q0, 1
q1}
q1 q2 q2
*q2 Ф Ф
14 Define Epsilon-NFA and convert the following Epsilon-NFA into DFA. 1

15 Convert the following NFA into DFA. 2

UNIT-2
Q. Blooms Course
Questions
No. Taxonomy Outcomes
level Mapped
1 Draw a DFSM for the following regular expression (i) aa*(a+b) (ii) 1
ab(a+b)* (ii) a*b*c*
2

2 Draw an epsilon-NFA for the regular expression R= (a+b)*bb(a+b)* 1

2
3 Define regular expression. Obtain a regular expression for the following 1
languages 2
i. L={an bm|(m+n) is even}
 ii. L= {w:|w|mod 3=0 , w ε {a,b}*}.
4 Define a regular expression. Draw the DFA for the regular expression 1
2
(i) (a+b)*a (ii) a(a+b)*b
5 Give the regular expression for the following languages on Σ= {a,b,c} 1
(i) All strings containing exactly one ‘a’.
2
(ii) All string that contains one occurrence of each symbol in Σ.
(iii) Even number of a’s or b’s or c’s.
6 Construct the regular expression depicted in the transition table by state 2
elimination method.
ᵟ a b Φ
→EE OE EO {EE,O
O}
OE EE OO {OE,E 2
O}
OO EO OE {OO,E
E}
*EO OO EE {EO,O
E}
7 Convert the following Finite Automata's into Regular Expressions by 2
eliminating possible states.

8 Let M = (Q, Σ, δ, q0, F) be a finite automata recognizing the language 1

L. Then there exists an equivalent regular expression R for the regular L 2
such that L = L(R).
9 Write the Regular Expression's for the following Languages. 1
i. To represent the strings of 0's and 1's starts and ends with same
symbols. 2
ii. To represent the strings of 0's and 1's such that the L={0n1m | m + n
is odd}
10 Convert the following Regular Expression's into Є -NFA. 2
i. (a+b)*ab(a+b)* + (a+b)*ba(a+b)* 2
ii. (0+1)*(01+10)
11 Convert the following Regular Expression's into Є -NFA. 2
i. (a+b)*ab(a+b)* + (a+b)*ba(a+b)* 2
ii. (0+1)*(01+10)
12 Represent the Regular Expressions for the following languages. 2
2
i. Strings of 0's and 1's having string length multiples of 3.
 ii. Strings of a's and b's which ends with bab.
iii. Strings of 0's and 1's such that odd number of 1's followed by even
number of 0's.
iv. Strings of a's and b's having no two consecutive b's.
13 List any 5 Algebraic Laws of Regular Expressions 1
2
14 Recursively we can define regular expression with basic regular 1
expressions. Define all those regular expressions recursively. 2

15 Find regular expression for the following Finite Automata by 1

eliminating states.

UNIT-3
Q. Blooms Course
Questions
No. Taxonomy Outcomes
level Mapped
1 State pumping lemma theorem for regular language and prove that the 1
language 1
L={ wwR| w ε {a,b}*} is not regular.
2 Define distinguishable and indistinguishable states. Minimize the DFA 1
depicted in
S 0 1
A B F
B G C
*C A C 3
D C G
E H F
F C G
G G E
H G C
3 Define grammar, derivation and sentential form with example. 1
3
4 Define ambiguity in grammar. Show the following grammar is 1
ambiguous.
S→ aB|bA 3
A→ aS|bAA|a
B→ bS|aBB|b
5 1
Let G be the grammar,
S→ aB|bA
3
A→ aS|bAA|a
B→ bS|aBB|b
For the string aaabbabbba find a (i) Left most derivation (ii) Right most
 derivation (iii) Parse tree
6 Show that the Following grammar is ambiguous. 1
S->aB | bA
3
A-> aS | bAA | a
B-> bS | aBB | b
7 Obtain the Grammar for the following Languages. 1
i. Strings of a's and b's with at least one a or one b.
ii. Strings of 0's and 1's having the substring 101. 2
iii. L={ anb2n | n>=0 }
iv. Set of all palindromes over Σ={0,1}
8 Pumping Lemma is to be applied to show that certain languages are not 1
regular. It should never be used to show a language is regular. State and 2
prove pumping lemma for regular languages
9 All languages are not regular. To prove certain languages are not 1
regular we use Pumping Lemma. Show that L = { anbn | n≥ 0} is not
2
regular

10 Define Context Free grammar. Design the context free grammars for the 1
following languages.
i) L = { an b2n : n ≥ 0}
3
ii) L = {wwR where w ϵ {a,b}* }

11 Define Ambiguous grammar. Obtain the string aaabbabbba by applying

left most derivation and the parse tree for the grammar shown below. Is
it possible to obtain the same string again by applying leftmost
derivation but by selecting different productions to prove it is
ambiguous? Justify the answer.

12 Discuss the applications of Context free grammars with examples. 1

3
13 Define Ambiguous grammar. Obtain the string aaabbabbba by applying 1
left most derivation and the parse tree for the grammar shown below. Is
it possible to obtain the same string again by applying leftmost
derivation but by selecting different productions to prove it is
ambiguous? Justify the answer. 3

14 If L1 and L2 are regular, then show that the regular language is closed 1
2
under intersection
15 1
Minimize the following DFA.
δ a b
3
->A B C
B D E
C F G
 *D D E
E F G
*F D E
*G F G
UNIT-4
Q. Blooms Course
Questions
No. Taxonomy Outcomes
level Mapped
1 4
Explain the following terms
(i) Push down automata (ii) Language of a PDA (iii) Instantaneous
description of PDA.
Convert the following CFG to PDA 3
S→ aABB|aAA
A→ aBB|a
B→ bBB|A
C→ a
2 Simplify the following grammar 1
S→ aA|a|Bb|cC
A→ aB
3
B→ a|Aa
C→ cCD
D→ ddd
3 Construct a PDA to accept the language L={ wwR| w ε {a,b}*}. 2
3
4 a) State pumping lemma for context free grammar. Show that the 1
language L= { anbncn | n≥0} is not context free. 2

5 For Certain languages there are no solution from the Finite Automata. 1
For those type of problems can be modeled by using PDA. Define the
3
PDA and Construct the PDA to accept the language L={anbn | n>=1}

6 Simplify the following Grammar. 1

S-> aA | a | B | C
A-> aB | Є
3
B-> aA
C-> cCD
D-> abd
7 Define GNF and CNF forms with an example. 1 2
8 Obtain a PDA to accept the language L= {WWR } over the strings of 2
0's or 1's and Show the instantaneous description of the PDA for the 3
string "001100".
9 Convert the following grammar into GNF form 2
S-> AA | 0 3
A-> SS | 1
10 Construct PDA for the language L= {wwR | w Є (a+b)*}. 2 3
11 Construct PDA for the language L= {anbn | a, b ϵ Σ n>= 0} 2 3
12 2
3
Convert the following grammar into corresponding PDA.
 S-> aABC
A-> aB | a
B-> bA| b
C -> a
13 Eliminate left recursion from the following grammar. 2
S -> Ab | a 3
A -> Ab | Sa
14 Obtain a PDA to accept the language L= {WWR } over the strings of 2
0's or 1's and Show the instantaneous description of the PDA for the 3
string "001100".
15 Simplify the following Grammar. 2
S-> aA | a | B | C
A-> aB | Є
3
B-> aA
C-> cCD
D-> abd

Course Coordinator Module Coordinator Director