JNTU B.Tech II FORMAL LANGUAGES AND AUTOMATA THEORY Previous Question Paper (July/August - 2021 - R16)

A Finite Automaton (FA) is a mathematical model of a system with a finite number of states that transitions between states based on input symbols. It is a 5-tuple (Q, Σ, δ, q0, F), where Q is a finite set of states, Σ is a finite set of input symbols (alphabet), δ is the transition function (Q × Σ → Q), q0 is the initial state, and F is the set of final states.

The model operates by reading an input string symbol by symbol. Starting at the initial state, the automaton uses the transition function to move to the next state based on the current state and the input character. If, after processing the entire string, the machine is in a state belonging to the set of final states, the string is accepted; otherwise, it is rejected.

To design an NFA for the language L = {0101^n | n > 0}, we define the states and transitions such that the machine recognizes the prefix '010' followed by one or more '1's.

• States: Q = {q0, q1, q2, q3, q4}
• Start state: q0
• Final state: F = {q4}
• Transitions:
• δ(q0, 0) = {q1}
• δ(q1, 1) = {q2}
• δ(q2, 0) = {q3}
• δ(q3, 1) = {q4}
• δ(q4, 1) = {q4}

The machine starts at q0, transitions through q1, q2, and q3 upon reading '010', and then stays in state q4 for any subsequent '1's, ensuring at least one '1' follows the initial '010' sequence.