Bsc CSIT Semester 4 – Theory of Computation – Unit II: Introduction to Finite Automata (8 Hrs.)

Question 1

Define the NFA with ε-transition and ε-closure of a state. Show that for every regular expression r, representing a language L, there is ε-NFA accepting the same language. Also convert regular express

Marks: 10

Year: 2076 Final TU

ε–NFA, ε–Closure, and Regular Expression Conversion Definition of ε–NFA An ε–NFA (Epsilon Non-Deterministic Finite Automaton) is defined as a 5–tuple: M = (Q, Σ, δ, q₀, F) Where: - Q → Finite set of

Question 2

Give the formal definition of DFA. Construct a DFA accepting all strings of {0, 1} with even number of 0’s and even number of 1’s.

Marks: 5

Year: 2076 Final TU

Definition (DFA) A Deterministic Finite Automaton is a 5-tuple M = (Q, Σ, δ, q₀, F) where: - Q is a finite set of states. - Σ is a finite input alphabet. - δ: Q × Σ → Q is the transition function (det

Question 3

Construct a NFA accepting language of {0, 1} with each string ending with 01 and convert it into equivalent DFA.

Marks: 5

Year: 2076 Final TU

Step 1: Description We need a machine that accepts all binary strings that end with "01". That is, L = { w ∈ {0,1} | w ends with 01 }. --- Step 2: NFA Construction An NFA can nondeterministically g

Question 4

Give the formal definition of DFA and NFA. How NFA can be converted into eqivalent DFA? Explain with suitable example.

Marks: 10

Year: 2078 Final TU

1. Deterministic Finite Automaton (DFA) A Deterministic Finite Automaton (DFA) is a mathematical model of computation that accepts or rejects strings over an input alphabet. A DFA is formally defined

Question 5

Find the minimum state DFA for the given DFA below: | States | Input | | |--------|-------|---| | | 0 | 1 | | A | B | F | | B | E | C | | C | B | D | | D |

Marks: 10

Year: 2078 Final TU

Formal Definition of DFA A Deterministic Finite Automaton (DFA) is a 5-tuple M = (Q, Σ, δ, q₀, F) where: 1. Q = finite set of states 2. Σ = input alphabet 3. δ : Q × Σ → Q = transition function

Question 6

Show that, For any NFA N=(Q, ∑, δ, q0, F) accepting language L=∑, There is a DFA D= (Q’, ∑’, q0′, δ’, F’) accepting the same language L.

Marks: 10

Year: 2079 Final TU

For any NFA $N=(Q,\Sigma,\delta,q0,F)$ that accepts language $L(N)=\Sigma^$, there exists a DFA $$D=(Q',\Sigma,q0',\delta',F')$$ such that $L(D)=L(N)=\Sigma^$. --- 1. Construction of the DFA (5 m

Question 7

State and prove the Pumping Lemma for regular languages. How can you show with example that pumping lemma is used to prove that a given language is not a regular? Explain.

Marks: 10

Year: 2079 Final TU

1. Statement of the Pumping Lemma for Regular Languages (2 marks) Let $L$ be an infinite regular language. Then there exists an integer $p\ge 1$ (called the pumping length) such that for every string

Question 8

Explain the ε-closure of states on an ε-NFA with suitable examples.

Marks: 5

Year: 2079 Final TU

ε-Closure of States in an ε–NFA (Exam-style Answer) In an ε–NFA (Epsilon–NFA), transitions can occur without consuming any input symbol, i.e., on ε (epsilon). To handle such automata, the concept of

Question 9

What is NFA? How is it different from DFA? How is NFA to DFA conversion done? Convert the following NFA into DFA.

Marks: 10

Year: 2080 Final TU

1. What is NFA? (2 Marks) A Nondeterministic Finite Automaton (NFA) is a 5-tuple: \[ N = (Q, \Sigma, \delta, q0, F) \] where, - $Q$: set of states - $\Sigma$: input symbols - $\delta$:

Question 10

Design a DFA that accepts single line and multi-line comments of the C-Language.

Marks: 5

Year: 2080 Final TU

Alphabet (classes): /, , \n (newline), other (any char ≠ /,,\n) Informal language: exactly one C comment — either a single-line //... (until end) or a closed multi-line / ... / (no nesting). States (s

Question 11

Describe the extended transition function of NFA. Construct a NFA, using transition table and transition diagram , over {0, 1} that accept the string having substring 01 and ends with 1. Show the acce

Marks: 10

Year: 2080 Final TU

1. Extended transition function of an NFA (δ) For an NFA $N=(Q,\Sigma,\delta,q0,F)$ the extended transition function $\delta^: Q \times \Sigma^ \to \mathcal P(Q)$ is defined recursively to describ

Question 12

Design a Melay machine over {a, b} that generates output ‘A’ if the input string ends with aa else output ‘B’ if the string ends with bb.

Marks: 5

Year: 2080 Final TU

Concept A Mealy Machine gives output on transitions, not on states. To check last two input symbols, the machine must remember the previous symbol. --- Mealy Machine Components - Input alphabet (Σ)