automata theory and formal language

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 = {�, �}.
 Problem-2: Design a DFA which accepts all strings with no more than
three a’s defined over the input alphabet = {�, �}.
 Problem-3: Design a DFA which accepts all strings with at least one ‘a’ and
exactly two b’s defined over the input alphabet = {�, �}.
 Problem-4: Design a DFA which accepts the following language defined
over the input alphabet = {�, �}.
� = {��5 ��2 : � ∈ �, � ∗ }

 Problem-5: Design a DFA which accepts the following language defined
over the input alphabet = {�, �}.
� = { � : � ��� 5 = 0 , � ∈ �, � ∗ }



Session-4: Non-Deterministic Finite Automtata

 Problem-1: Design a NFA with three states that accepts the language � =
{��, ���}∗ .
 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 � = �� : � ≥ 0 ∪ {�� � : � ≥ 1}

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




Instructor: Asesh Kumar Tripathy, CSE(H), KLU Section: ATFL - S02