1 2

Q1. Difference Between Moore Machine and Mealy Machine 2. Σ: Alphabet, a finite set of symbols that the automaton can read.
3. δ (Transition Function): Defines rules for moving between states, δ: Q × Σ → Q for DFA and δ: Q × (Σ
Moore Machine Mealy Machine {ε}) → P(Q) for NFA.
[Link] depends only upon the present state. [Link] depends on the present state as well as 4. q₀ (Initial State): The state where computation begins.
5. F (Final States): Subset of Q indicating where input strings are accepted.
present input.
The automaton processes input strings symbol by symbol, transitioning according to
2. Moore machine also places its output in the 2. Mealy Machine places its output on the δ. If the automaton ends in a state in F after reading all inputs, the string is accepted.
state. transition.
Q5. Describe all the Production Rules
[Link] states are required. [Link] number of states are required. Ans: In formal grammar (used in automata theory), production rules define how symbols in a language are
[Link] machines requires more hardware [Link] Machines requires less hardware replaced. They are written as A → α, where:
requirement for circuit implementation. requirement for circuit implementation. 1. A: Non-terminal symbol to be replaced.
2. α: String of terminals and/or non-terminals. Types of production rules:
[Link] react slower to inputs(One clock cycle [Link] react faster to inputs. • Terminal Production: Non-terminal replaced by a terminal (e.g., A → a).
later). • Non-terminal Production: Non-terminal replaced by other non-terminals (e.g., A → BC).
[Link] output and state generation. 6. Asynchronous output generation. • Mixed Production: Combination of terminals and non-terminals (e.g., A → aB).
• Epsilon Production: Non-terminal replaced by ε (empty string).
8. Easy to design. 8. It is difficult to design. These rules form the backbone of grammars, categorized into Chomsky's hierarchy (regular, context-free,
context-sensitive, and unrestricted grammars).
Q6.
Q2. Model of Finite Automata
Ans: Finite Automata (FA) is a mathematical model used to represent a system with a finite number of
states. It consists of:
1. States (Q): A finite set of states, including an initial and accepting states.
2. Alphabet (Σ): A set of symbols representing valid inputs.
3. Transition Function (δ): Defines state transitions based on inputs.
4. Initial State (q₀): The starting state of the automaton.
5. Accepting States (F): Subset of states where input strings are accepted.
FA operates step-by-step, reading inputs and transitioning states according to δ. It halts when no valid
transition exists or all inputs are processed. FA is categorized into Deterministic (DFA) and Non-
Deterministic (NFA). DFA has one transition per input per state, while NFA can have multiple.

Q3. Comparison Between DFA and NFA

• Definition: DFA (Deterministic Finite Automaton) has one transition per input per state, while NFA
(Non-Deterministic Finite Automaton) can have multiple.
• Determinism: DFA operates deterministically; NFA allows multiple paths.
• Complexity: DFA is easier to simulate but harder to construct, whereas NFA is simpler to construct
but may require conversion to DFA for implementation.
• Transition: DFA has a single path for each input from a state. NFA can have multiple paths or ε-
transitions (empty moves).
• Acceptance: DFA accepts input if a single path leads to an accepting state. NFA accepts if any path
leads to an accepting state.
• Conversion: Every NFA can be converted to an equivalent DFA.
• Space: DFA may require exponentially more states than the corresponding NFA.

Q4. Tuples of Finite Automata

Ans: Finite Automata is represented as a 5-tuple (Q, Σ, δ, q₀, F):
1. Q: Finite set of states, representing possible system configurations.

1 2

3 4

Q7.

Q8.

3 4
 5 6

Q.11 List All the Production Rules of Grammar

Ans: A grammar consists of four parts: G=(N,T,P,S)G = (N, T, P, S), where PP represents the set of
production rules. A production rule specifies how variables (non-terminals) can transform into terminals or
other variables. Examples include:
1. S→ABS \to AB
2. A→aAaA \to aA | a
3. B→bBbB \to bB | b

Q.12 Describe Linear Bounded Automata with Suitable Example

Ans: A Linear Bounded Automaton (LBA) is a non-deterministic Turing Machine with a tape of finite length
proportional to the input size. It operates within bounded space and is used for context-sensitive
languages.
Example: For L={anbncn n≥1}L = \{ a^n b^n c^n \mid n \geq 1 \}, an LBA verifies the count of a,b,ca, b, c
matches, unlike a PDA.

Q.13 What is Halting Problem

Ans: The Halting Problem is a fundamental concept in computer science and mathematical logic. It was first
introduced by Alan Turing in 1936 and is one of the earliest examples of a decision problem that can be
proven to be undecidable.
Definition:
 The Halting Problem asks whether there exists an algorithm that can determine, for any arbitrary
program and input, whether the program will eventually halt (terminate) or run forever without halting.
Key Points:
Q.10 Explain Turing Machine with a Suitable Diagram  Undecidability: The Halting Problem is proven to be undecidable, meaning no algorithm can solve
Ans: A Turing Machine is a theoretical computing model proposed by Alan Turing. It consists of: the problem for all possible program-input pairs. There is no general method to determine whether any
1. Tape: An infinite tape divided into cells, each holding a symbol from a finite alphabet. given program will halt or not.
2. Head: Reads and writes symbols on the tape and moves left or right.  Proof by Contradiction: Turing's proof uses a technique called "proof by contradiction." He shows
3. States: A finite set of states representing the current context. that if such an algorithm (a hypothetical halting decider) existed, it would lead to a logical contradiction.
4. Transition Function: Dictates the machine's actions based on the current state and tape symbol.  Implications: The undecidability of the Halting Problem has significant implications for the limits of
5. Accept and Reject States: Special states determining if input is accepted or rejected. computation. It demonstrates that there are inherent limitations to what can be computed or decided
Turing Machines can simulate any algorithm and are used to define computational limits. algorithmically.

5 6

7 8

 Simplified Explanation: Imagine you have a magic box that can analyze any computer program and tell 3. Conversion to Regular Expressions:
you if the program will eventually stop or run forever. The Halting Problem shows that it is impossible to  NFAs with ε-transitions are closely related to regular expressions and can be used to construct them
build such a magic box that works correctly for every possible program and input. more easily. The ε-transitions can represent the empty string, making it easier to handle optional parts of
the language.
Q.14 Describe Greibach Normal Form (GNF) 4. Equivalence to DFAs:
Ans: A Context-Free Grammar (CFG) is in Greibach Normal Form if all productions are of the form:  Despite the apparent extra power of NFAs with ε-transitions, they are equivalent to DFAs in terms of
A→aα the languages they can recognize. Any language that can be recognized by an NFA with ε-transitions
can also be recognized by a DFA.
where:
5. Algorithmic Applications:
 A is a non-terminal.
 NFAs with ε-transitions are often used in algorithms for lexical analysis, parsing, and other areas of
 a is a single terminal symbol. computer science where automata are applied. They provide a more flexible framework for constructing
 α is a (possibly empty) string of non-terminal symbols. and analyzing state machines.
This format ensures that the derivation of any string in the language starts with a terminal symbol, making
it particularly useful for designing parsers. In summary, NFAs with null moves (ε-transitions) offer a more expressive and flexible way to design finite
automata, making them a valuable tool in the theory of computation and its applications.
Q.15 Show That (a+b)∗=(a∗b∗)∗(a + b)^* = (a^* b^*)^*
Ans: To prove that (a+b)∗=(a∗b∗)∗ in the context of formal languages and the theory of computation, we'll Q.17 Define Pumping Lemma
need to show that both expressions generate the same set of strings. Ans: There are two Pumping Lemmas, which are defined for 1. Regular Languages, and 2. Context – Free
Left-Hand Side: (a+b)∗ Languages Pumping Lemma for Regular Languages For any regular language L, there exists an integer n,
This represents the set of all strings (including the empty string) that can be formed by concatenating any such that for all x ? L with |x| ? n, there exists u, v, w ? ?*, such that x = uvw, and (1) |uv| ? n (2) |v| ? 1 (3)
number of a's and b's in any order.
for all i ? 0: uviw ? L In simple terms, this means that if a string v is ‘pumped’, i.e., if v is inserted any
Right-Hand Side: (a∗b∗)∗
This expression can be understood as follows: number of times, the resultant string still remains in L. Pumping Lemma is used as a proof for irregularity
 a^* denotes any number (including zero) of a's. of a language. Thus, if a language is regular, it always satisfies pumping lemma. If there exists at least one
 b^* denotes any number (including zero) of b's. string made from pumping which is not in L, then L is surely not regular. The opposite of this may not
 When concatenated, a^* b^* represents any number of a's followed by any number of b's. always be true. That is, if Pumping Lemma holds, it does not mean that the language is regular.
The outer ∗ then allows for any number of repetitions of the pattern a^* b^*.
Proof:
LHS to RHS:
 Any string generated by (a + b)^* can be broken into segments where each segment consists of zero or
more a's followed by zero or more bb's.
 This segmentation is exactly what (a^* b^*)^* generates because it allows any number of such For example, let us prove L01 = {0n1n | n ? 0} is irregular. Let us assume that L is regular, then by Pumping
segments. Lemma the above given rules follow. Now, let x ? L and |x| ? n. So, by Pumping Lemma, there exists u, v, w
RHS to LHS: such that (1) – (3) hold. We show that for all u, v, w, (1) – (3) does not hold. If (1) and (2) hold then x =
 Any string generated by (a^* b^*)^* is a sequence where each segment consists of zero or more a's 0n1n = uvw with |uv| ? n and |v| ? 1. So, u = 0a, v = 0b, w = 0c1n where : a + b ? n, b ? 1, c ? 0, a + b + c = n
followed by zero or more bb's. But, then (3) fails for i = 0 uv0w = uw = 0a0c1n = 0a + c1n ? L, since a + c ? n.
 All such sequences are possible strings of concatenated a's and b's, which is exactly what (a + b)^*
generates. Q.18 Show That L={ap∣p is prime}L = \{ a^p \mid p \text{ is prime} \} Is Not a Regular Language
 Thus, both expressions describe the same set of strings, proving that (a + b)^* = (a^* b^*)^*. Ans: As a reminder and clarification of notation: The pumping lemma states that any
word w∈L with |w|> n for a specific n can be split into three parts w=abc so that:
Q.16 Significance of NFA with Null Moves 1. |ab|≤n
Ans: Non-deterministic Finite Automata (NFA) with null moves, also known as ε-transitions (epsilon 2. |b|>0
transitions), are a powerful concept in automata theory. These automata allow transitions to occur without 3. ∀i∈N::abic ∈ L
consuming any input symbols, meaning the automaton can change states "for free." Here’s a brief overview
Suppose there exists such an n (which must be true if L is regular). Then there is also a partition of any
of their significance:
word z=abc with |z|>n which fulfills the above criteria.
1. Simplification of Design:
 NFAs with ε-transitions can simplify the construction of automata for certain languages. They allow for It is clear that the word zi=abic is of length
|zi|=|ac|+i|b|
more flexible and concise representations compared to deterministic finite automata (DFAs).
and thus
2. State Reduction:
|zi|≡|ac| (mod |b|)
 Using ε-transitions can potentially reduce the number of states required to recognize a particular And
language. This can make the automaton more compact and easier to understand. |zi|≡|ac|−i (mod |b|+1)
7 8
 9 10

In the case i=|ac|,

|zi|≡0 (mod |b|+1)
holds true. In other words, |z|ac||would be divisible by |b|+1.
Obviously, |zi|≠|b|+1 in the general case, so z|ac| would therefore not be prime and could not possibly
be element of L. So there has to exist a word z=abc with |z|>n for which abic is not in the language,
independently of n or the choice of a, b and c. Therefore, L can not be regular.

Q.19 What Is Arden’s Theorem Right Most Derivation (RMD) : Rightmost derivation of a string from starting symbol S is done by replacing
Ans: Arden’s theorem state that: “If P and Q are two regular expressions over “∑”, and if P does not contain rightmost non-terminal symbol by RHS of corresponding production rule. e.g.; The rightmost derivation of
“∈” , then the following equation in R given by R = Q + RP has a unique solution i.e., R = QP*.” That means, string abab from grammar G above is done as :
whenever we get any equation in the form of R = Q + RP, then we can directly replace it with R = QP*. So, S => SS => SaSb => Sab => aSbab => abab
here we will first prove that R = QP* is the solution of this equation and then prove that it is the unique The symbols underlined are replaced using production rules. The derivation tree for abab using rightmost
solution of this equation. Let’s start by taking this equation as equation (i) derivation has been shown in Figure 2.
1. proof R = QP* is the solution of R = Q + RP
R = Q + RP ......(i)
Now, replacing R by R = QP*, we get,
R = Q + QP*P
Taking Q as common,
(As we know that ∈ + R*R = R*). Hence proved. Thus, R = QP* is the solution of the equation R = Q + RP.
Now, we have to prove that this is the only solution to this equation.
2. proof R = QP* is the unique solution of R = Q + RP
Let me take this equation again: A derivation can be either LMD or RMD or both or none. For example, S => aSb => abSab => abab is LMD as
R = Q + RP well as RMD but S => SS => SaSb => Sab => aSbab => abab is RMD but not LMD.
Now, replace R by R = Q + RP, Ambiguous Context Free Grammar : A context free grammar is called ambiguous if there exists more than
R = Q + (Q + RP)P = Q + QP + RP2 one LMD or more than one RMD for a string which is generated by grammar. There will also be more than
Again, replace R by R = Q + RP :- one derivation tree for a string in ambiguous grammar. The grammar described above is ambiguous
R = Q + QP + (Q + RP) P2 = Q + QP + QP2 + RP3 because there are two derivation trees (Figure 1 and Figure 2). There can be more than one RMD for string
. abab which are:
. S => SS => SaSb => Sab => aSbab => abab
= Q + QP + QP2 + .. + Q + RP(n+1) S => aSb => abSab => abab
Now, replace R by R = QP*, we get, Ambiguous Context Free Languages : A context free language is called ambiguous if there is no
unambiguous grammar to define that language and it is also called inherently ambiguous Context Free
R = Q + QP + QP2 + .. + QPn+ QP*
Languages.
Taking Q as common,
eg- L={anbncm} U {anbmcm}
R = Q( ∈ + P + P2 + .. + Pn + P*P(n+1) = QP* [As ∈ + P + P2 + .. + Pn + P*P(n+1)
Note :
represent the closure of P]
a. If a context free grammar G is ambiguous, language generated by grammar L(G) may or may not be
Hence proved. Thus, R = QP* is the unique solution of the equation R = Q + RP.
ambiguous.
Q.20 Explain Ambiguity in Context-Free Grammars b. It is not always possible to convert ambiguous CFG to unambiguous CFG. Only some ambiguous CFG
Ans: Suppose we have a context free grammar G with production rules : S -> aSb | bSa | SS | e can be converted to unambiguous CFG.
Left Most Derivation (LMD) and Derivation Tree : Leftmost derivation of a string from starting symbol S is c. There is no algorithm to convert ambiguous CFG to unambiguous CFG.
done by replacing leftmost non-terminal symbol by RHS of corresponding production rule. For example, d. There always exists a unambiguous CFG corresponding to unambiguous CFL.
the leftmost derivation of string abab from grammar G above is done as : e. Deterministic CFL are always unambiguous and are parsed by LR parsers.
S => aSb => abSab => abab
The symbols underlined are replaced using production rules.
Derivation Tree : It tells how a string is derived using production rules from S and has been shown in Figure
1.

9 10