Automata theory and formal language Problems

Automata Theory and Formal Languages (ATFL) - ODD Sem 2022-23
Problem Sets for Course Outcome – 1

Session -1 : No Problems required – Introduction only
Session -2: No Problems required

Session-3: Deterministic Finite Automata

 Problem-1: Design a DFA which accepts all strings with exactly one ‘a’
defined over the input alphabet ∑ ¿{a , b }.
 Problem-2: Design a DFA which accepts all strings with no more than
three a’s defined over the input alphabet ∑ ¿{a , b }.
 Problem-3: Design a DFA which accepts all strings with at least one ‘a’ and
exactly two b’s defined over the input alphabet ∑ ¿{a , b }.
 Problem-4: Design a DFA which accepts the following language defined
over the input alphabet ∑ ¿{a , b }.
¿
L={a b5 w b 2 :w ∈ { a , b } }

 Problem-5: Design a DFA which accepts the following language defined
over the input alphabet ∑ ¿{a , b }.
¿
L={w :|w|mod 5=0 , w ∈ {a , b } }



Session-4: Non-Deterministic Finite Automtata

 Problem-1: Design a NFA with three states that accepts the language
L={ab , abc }¿.
 Problem-2: Which of the strings 00, 01001, 10010, 000, 0000 are
accepted by the following NFA




 Problem-3: Design a NFA with four states which accepts the following
Language L= { an :n ≥0 } ∪{bn a :n ≥1 }

 Problem-4: Design a NFA with three states which accepts the following
Language