1. What is FA? Enlist its types.

A Finite Automaton (FA) is a theoretical machine used to recognize patterns within strings
and model computation. It consists of a finite set of states, an initial state, a set of
final/accepting states, and a transition function that defines how the machine moves between
states based on input symbols.

Types of Finite Automaton (FA):

• Deterministic Finite Automaton (DFA): A finite automaton where for each state
and input symbol, there is exactly one transition to a new state.
• Non-deterministic Finite Automaton (NFA): A finite automaton where for a given
state and input symbol, there can be multiple possible transitions, including no
transition.
• NFA with ε (epsilon) transitions: A type of NFA that allows transitions without
consuming any input symbol, i.e., the machine can move to a new state on an epsilon
(empty string) transition.
• Mealy Machine: A finite state machine where the output depends on both the current
state and the input symbol.
• Moore Machine: A finite state machine where the output depends only on the current
state.

2. What is the necessity of converting an NFA to a DFA?

The necessity of converting an NFA to a DFA arises from the fact that while NFAs are easier
to design due to their non-deterministic nature, DFA is more suitable for practical
implementation. A DFA is easier to simulate and implement on a computer because it has
exactly one state for each possible input at any given time. Additionally:

• DFA guarantees efficiency in processing strings (since there is no ambiguity in state

transitions).
• DFA has faster execution times because it avoids the need for backtracking or
maintaining multiple possible states at once, as in an NFA.
• NFA can recognize the same languages as DFA, but the conversion ensures that we
can work with a model that is computationally simpler and easier to implement.

3. What is null string and length of string? Explain with example.

• Null String (ε): The null string or empty string is a string that contains no
characters. It is denoted by ε or λ.
o Example: The string ε has no characters.
• Length of a String: The length of a string is the number of symbols (characters) in
the string. It is denoted as |w|, where w is the string.
o Example: The string "abc" has a length of 3, i.e., |abc| = 3.
o For the null string ε, the length is 0, i.e., |ε| = 0.

4. Write a short note on: NFA with ε-Transitions to DFA.

An NFA with ε-transitions is a non-deterministic finite automaton that allows transitions
between states without consuming any input symbols. These transitions are called epsilon
transitions (or λ-transitions).

To convert an NFA with ε-transitions to a DFA, we follow these steps:

1. Epsilon Closure: For each state in the NFA, compute its epsilon closure, which is
the set of states that can be reached from the current state via epsilon transitions.
2. New States: Treat each epsilon closure as a state in the resulting DFA.
3. Transitions: The transition function of the DFA is derived by considering all possible
input symbols, using the epsilon closures for each state.
4. Final States: Any state in the DFA that includes a final state from the NFA is a final
state in the DFA.

5. Describe DFA as pattern recognizer in detail.

A DFA is used as a pattern recognizer in various applications such as lexical analysis in

compilers, string matching, and regular expression matching.

Working of DFA as a pattern recognizer:

• The DFA starts in an initial state and reads the input string symbol by symbol.
• For each input symbol, the DFA moves to a new state as dictated by its transition
function.
• The DFA continues processing the input until it has read the entire string.
• If, at the end of the string, the DFA is in an accepting state, the input string is
accepted as a match for the recognized pattern.
• If the DFA is in a non-accepting state at the end of the string, the pattern is rejected.

For example, a DFA can be designed to recognize whether a given string contains an even
number of 1s by having two states: one for even counts and one for odd counts. The DFA
accepts the string if it ends in the "even" state.

6. With the help of example describe Myhill-Nerode method for NFA to DFA.

The Myhill-Nerode theorem provides a method for determining the minimal number of
states required in a DFA that recognizes the same language as a given NFA. The method
works by identifying equivalence classes of strings, which help in minimizing the DFA.

Steps for Myhill-Nerode method:

1. Define equivalence classes: Two strings are said to be equivalent if, for every string
that can be concatenated to them, the resulting string belongs to the language or not in
the same way. This means that the DFA, after reading these two strings, will behave
the same regardless of the remaining input.
2. Partition the strings: The set of all strings over the alphabet is partitioned into
equivalence classes.
3. Construct states for DFA: Each equivalence class corresponds to a state in the
minimized DFA. Transitions between these states are defined based on the
equivalence of concatenated strings.
Example: If we want to construct a DFA for the language "strings that contain an even
number of 0s", equivalence classes can be defined based on the number of 0s modulo 2.
There are two equivalence classes: one for strings that have an even number of 0s, and one
for strings with an odd number of 0s.

7. Describe NFA with ε-transitions with example.

An NFA with ε-transitions (or ε-NFA) is an NFA where the automaton can transition
between states without consuming any input symbol. These transitions allow the automaton
to move from one state to another without reading any characters.

Example: Consider an NFA with states q0q_0q0, q1q_1q1, and q2q_2q2, where:

• q0q_0q0 is the initial state.

• q2q_2q2 is an accepting state.
• The transition from q0q_0q0 to q1q_1q1 can happen without reading any input (ε-
transition).
• The transition from q1q_1q1 to q2q_2q2 occurs on reading input symbol 'a'.

This means that the machine can go from q0q_0q0 to q1q_1q1 without reading any input and
can then transition from q1q_1q1 to q2q_2q2 when reading 'a'. The string 'a' would be
accepted because the automaton can move through the epsilon transition and reach an
accepting state.

8. Construct a DFA to accept the set of all strings over {0, 1} such that every
pair of adjacent 0's appears before any pair of adjacent 1's.

The DFA needs to recognize strings where:

• Every occurrence of two consecutive 0's (00) must appear before any occurrence of
two consecutive 1's (11).

DFA construction:

• States: q0q_0q0 (initial state), q1q_1q1 (seen 0), q2q_2q2 (seen 00), q3q_3q3 (seen
1), q4q_4q4 (error state).
• Transition table:
o q0q_0q0 → q1q_1q1 on '0', q0q_0q0 → q3q_3q3 on '1'.
o q1q_1q1 → q2q_2q2 on '0', q1q_1q1 → q3q_3q3 on '1'.
o q2q_2q2 → q3q_3q3 on '1', stay in q2q_2q2 on '0'.
o q3q_3q3 → q4q_4q4 on '0', q3q_3q3 → q4q_4q4 on '1'.
o q4q_4q4 is a dead state.

Accepting states: q2q_2q2 and q3q_3q3.

9. Construct DFA for language over alphabet {a, b} which accepts all strings
containing 'a' at every even position in the string.
The DFA should accept strings where 'a' appears in every even position (2, 4, 6, ...) of the
string.

DFA construction:

• States: q0q_0q0 (initial state), q1q_1q1 (odd position, expecting 'b'), q2q_2q2 (even
position, expecting 'a').
• Transition table:
o q0q_0q0 → q1q_1q1 on 'a', q0q_0q0 → q2q_2q2 on 'b'.
o q1q_1q1 → q1q_1q1 on 'a', q1q_1q1 → q2q_2q2 on 'b'.
o q2q_2q2 → q1q_1q1 on 'a', q2q_2q2 → q1q_1q1 on 'b'.

Accepting states: q0q_0q0, q2q_2q2.

10. Construct NFA for language over alphabet {a, b} which accepts all strings
starting with 'a' and not having the substring 'bbb' in it.

NFA construction:

• States: q0q_0q0 (start), q1q_1q1, q2q_2q2 (seen 'bb'), q3q_3q3 (error state, seen
'bbb').
• Transition table:
o q0q_0q0 → q1q_1q1 on 'a', q0q_0q0 → q0q_0q0 on 'b'.
o q1q_1q1 → q1q_1q1 on 'a', q1q_1q1 → q2q_2q2 on 'b'.
o q2q_2q2 → q3q_3q3 on 'b', q2q_2q2 → q0q_0q0 on 'a'.
o q3q_3q3 is a dead state.

Accepting states: q0q_0q0, q1q_1q1, q2q_2q2

11. Construct DFA for L=L1∩L2L = L_1 \cap L_2L=L1∩L2, where:

• L1L_1L1: All strings starting with 'a' and containing an even number of 'b's over {a, b}.
• L2L_2L2: All strings containing an odd number of 'b's over {a, b}.

DFA Construction for L1∩L2L_1 \cap L_2L1∩L2:

To construct a DFA for the intersection of these two languages, we need to ensure both
conditions:

1. The string must start with 'a' and have an even number of 'b's (condition of L1L_1L1).
2. The string must contain an odd number of 'b's (condition of L2L_2L2).

• States:
o q0q_0q0: Initial state (even number of 'b's, no 'b' seen yet, start with 'a').
o q1q_1q1: Odd number of 'b's, no 'b' seen yet.
o q2q_2q2: Even number of 'b's, one 'b' seen.
o q3q_3q3: Odd number of 'b's, one 'b' seen.
• Transition table:
o q0q_0q0 → q1q_1q1 on 'a', q0q_0q0 → q2q_2q2 on 'b' (starts with 'a' and first 'b'
encountered).
 o q1q_1q1 → q3q_3q3 on 'b', stays in q1q_1q1 on 'a'.
o q2q_2q2 → q3q_3q3 on 'b', stays in q2q_2q2 on 'a'.
o q3q_3q3 → q2q_2q2 on 'b', stays in q3q_3q3 on 'a'.
• Accepting States:
o q2q_2q2, q3q_3q3 (because in these states, the conditions for both L1L_1L1 and
L2L_2L2 hold).

13. Construct DFA for the following languages:

(i) Set of all strings which contain exactly two 'c's anywhere over {a, b, c}.

• States:
o q0q_0q0: No 'c' seen.
o q1q_1q1: One 'c' seen.
o q2q_2q2: Two 'c's seen (final state).
o q3q_3q3: More than two 'c's (dead state).
• Transition table:
o q0q_0q0 → q1q_1q1 on 'c', stays in q0q_0q0 on 'a', 'b'.
o q1q_1q1 → q2q_2q2 on 'c', stays in q1q_1q1 on 'a', 'b'.
o q2q_2q2 → q3q_3q3 on 'c', stays in q2q_2q2 on 'a', 'b'.
• Accepting state: q2q_2q2 (because exactly two 'c's should be present).

(ii) Set of strings over {0, 1} whose second and second last symbol is '1'.

• States:
o q0q_0q0: Initial state, no positions processed.
o q1q_1q1: First symbol is 1.
o q2q_2q2: Second symbol is 1 (valid position).
o q3q_3q3: Second last symbol is 1.
o q4q_4q4: Invalid state (error state).
• Transition table:
o q0q_0q0 → q1q_1q1 on '1', q0q_0q0 → q0q_0q0 on '0'.
o q1q_1q1 → q2q_2q2 on '1', q1q_1q1 → q4q_4q4 on '0'.
o q2q_2q2 → q3q_3q3 on '1', q2q_2q2 → q4q_4q4 on '0'.
o q3q_3q3 → q3q_3q3 on '1' or '0' (any input maintains state).
• Accepting state: q3q_3q3 (second and second last positions are '1').

(iii) All strings over {0, 1} in which every even position in the string is occupied by 0 and odd position by
1.

• States:
o q0q_0q0: Start state (expect 1 in odd positions and 0 in even positions).
o q1q_1q1: Odd position, expecting '1'.
o q2q_2q2: Even position, expecting '0'.
• Transition table:
o q0q_0q0 → q1q_1q1 on '1', q0q_0q0 → q2q_2q2 on '0'.
o q1q_1q1 → q2q_2q2 on '0'.
o q2q_2q2 → q1q_1q1 on '1'.
• Accepting state: q1q_1q1, q2q_2q2 (both valid for even and odd positions).
(iv) Which accepts all strings starting with '01' and having substring '012' in it.

• States:
o q0q_0q0: Initial state.
o q1q_1q1: '0' seen.
o q2q_2q2: '01' seen.
o q3q_3q3: '012' seen (final state).
o q4q_4q4: Error state (if '012' does not appear).
• Transition table:
o q0q_0q0 → q1q_1q1 on '0'.
o q1q_1q1 → q2q_2q2 on '1'.
o q2q_2q2 → q3q_3q3 on '2'.
o q3q_3q3 stays in q3q_3q3 on any input.
o q4q_4q4 stays in q4q_4q4 (dead state).
• Accepting state: q3q_3q3 (because the string starts with '01' and contains '012').

(v) All strings starting with '10' and having substring '201' in it.

• States:
o q0q_0q0: Initial state (start with '10').
o q1q_1q1: '1' seen, expecting '0'.
o q2q_2q2: '10' seen, expecting '201'.
o q3q_3q3: '201' seen (final state).
o q4q_4q4: Error state.
• Transition table:
o q0q_0q0 → q1q_1q1 on '1'.
o q1q_1q1 → q2q_2q2 on '0'.
o q2q_2q2 → q3q_3q3 on '2'.
o q3q_3q3 stays in q3q_3q3 on '1', '0', or '2'.
• Accepting state: q3q_3q3.

(vi) All strings over {0, 1} such that if it starts with 0 then it contains even number of 0's and if it starts
with 1 then it contains odd number of 1's.

• States:
o q0q_0q0: Initial state (start with 0, even number of 0's).
o q1q_1q1: Odd number of 0's seen.
o q2q_2q2: Even number of 1's seen after starting with 1.
o q3q_3q3: Odd number of 1's seen after starting with 1.
• Transition table:
o q0q_0q0 → q1q_1q1 on '0', q2q_2q2 on '1'.
o q1q_1q1 → q0q_0q0 on '0', stays in q1q_1q1 on '1'.
o q2q_2q2 → q3q_3q3 on '1', stays in q2q_2q2 on '0'.
o q3q_3q3 → q2q_2q2 on '1', stays in q3q_3q3 on '0'.
• Accepting state: q0q_0q0, q2q_2q2.

(vii) Language over alphabet {0, 1, 2} which accepts all strings containing at least one occurrence of
the double symbol.

• States:
o q0q_0q0: Initial state, no '11' seen.
 o q1q_1q1: '1' seen, waiting for the next '1'.
o q2q_2q2: '11' seen (final state).
• Transition table:
o q0q_0q0 → q1q_1q1 on '1', stays in q0q_0q0 on '0' or '2'.
o q1q_1q1 → q2q_2q2 on '1', stays in q1q_1q1 on '0' or '2'.
o q2q_2q2 stays in q2q_2q2 on any input.
• Accepting state: q2q_2q2.

14. Design a Moore machine for binary input sequence such that if it has a
substring '101', the machine outputs 'A', if it has a substring '110', the
machine outputs 'B', otherwise it outputs 'C'.

Moore Machine Design:

• States:
o q0q_0q0: Initial state (output 'C').
o q1q_1q1: '1' seen (output 'C').
o q2q_2q2: '10' seen (output 'C').
o q3q_3q3: '101' seen (output 'A').
o q4q_4q4: '110' seen (output 'B').
• Transition table:
o q0q_0q0 → q1q_1q1 on '1', stays in q0q_0q0 on '0'.
o q1q_1q1 → q2q_2q2 on '0', stays in q1q_1q1 on '1'.
o q2q_2q2 → q3q_3q3 on '1', q4q_4q4 on '1'.
o q3q_3q3, q4q_4q4 stays in their respective states.

15. Design a Mealy machine which outputs EVEN or ODD according to the
number of '1's encountered is even or odd over {0, 1}.

Mealy Machine Design:

• States:
o q0q_0q0: Even number of '1's (output "EVEN").
o q1q_1q1: Odd number of '1's (output "ODD").
• Transition table:
o q0q_0q0 → q1q_1q1 on '1', stays in q0q_0q0 on '0'.
o q1q_1q1 → q0q_0q0 on '1', stays in q1q_1q1 on '0'.

16. Write a mapping of 'd' in case of NFA and DFA.

• For NFA, d(q,a)d(q, a)d(q,a) can be a set of states. This is because from a given state qqq, on
reading input symbol aaa, the NFA can transition to multiple states.
• For DFA, d(q,a)d(q, a)d(q,a) is a single state. From a given state qqq, on reading input symbol
aaa, the DFA will transition to exactly one state.

17. Differentiate between Moore and Mealy machine.

 Moore Machine Mealy Machine

Outputs are associated with states. Outputs are associated with transitions.

Output depends on both the current

Output depends only on the current state.
state and the input.

The output can change immediately

The output changes only when the state changes.
after reading an input symbol.

More states may be required to represent the same Mealy machines are typically more
behavior compared to Mealy machines. compact than Moore machines.

1. What is regular language? Explain with example.

A regular language is a type of formal language that can be described by a regular

expression or recognized by a finite automaton (deterministic or non-deterministic).
Regular languages are the simplest class in the Chomsky hierarchy of languages, and they are
closed under operations like union, intersection, complementation, and concatenation.

Example:

• The language L={an∣n≥0}L = \{a^n \mid n \geq 0\}L={an∣n≥0} is regular because it consists of
strings with only 'a' repeated zero or more times. This can be described by the regular
expression a∗a^*a∗, and can be recognized by a finite automaton that simply loops on the
symbol 'a'.

Another example:

• The language L={w∣w ends with ’ab’}L = \{w \mid w \text{ ends with 'ab'}
\}L={w∣w ends with ’ab’} over Σ={a,b}\Sigma = \{a, b\}Σ={a,b} is regular. It can be represented
by the regular expression (a+b)∗ab(a + b)^*ab(a+b)∗ab, which matches any string that ends
with "ab".

2. What is regular expression? Explain with example.

A regular expression (regex or regexp) is a symbolic representation of a pattern for

matching strings in a language. It defines a set of strings by using special characters like
union (+), concatenation (juxtaposition), and Kleene star (*), which denotes repetition.

Example:

For the alphabet Σ={a,b}\Sigma = \{a, b\}Σ={a,b}, the following are regular expressions and
their corresponding meanings:

• a∗a^*a∗: Matches any number of 'a's, including zero (e.g., "", "a", "aa", "aaa", ...).
 • (a+b)∗(a + b)^*(a+b)∗: Matches any string of 'a's and 'b's, including the empty string (e.g., "",
"a", "b", "ab", "baa", ...).
• a(b+a)∗ba(b + a)^*ba(b+a)∗b: Matches a string that starts with 'a', ends with 'b', and can
have any combination of 'a's and 'b's in the middle (e.g., "ab", "aabb", "abaab", ...).

3. Describe in English the sets denoted by the following regular expressions:

(i) (11+0)∗(00+1)∗(11 + 0)^* (00 + 1)^*(11+0)∗(00+1)∗

• This regular expression describes strings where:

o The first part, (11+0)∗(11 + 0)^*(11+0)∗, matches any sequence of zero or more
occurrences of either "11" or "0". This can include strings of just "11"s, just "0"s, or
any combination of these (e.g., "", "11", "0", "110", "0", "11011", ...).
o The second part, (00+1)∗(00 + 1)^*(00+1)∗, matches any sequence of zero or more
occurrences of either "00" or "1" (e.g., "", "1", "00", "100", "0011", ...).

The complete expression matches strings formed by any combination of "11", "0",
"00", and "1".

(ii) (1+01+001)∗(ϵ+0+00)(1 + 01 + 001)^* (\epsilon + 0 + 00)(1+01+001)∗(ϵ+0+00)

• This regular expression describes strings that:

o Begin with any number (zero or more) of repetitions of the substrings "1", "01", or
"001".
o The string ends with either the empty string ϵ\epsilonϵ, "0", or "00".

This allows strings like "", "1", "001", "01", "0011", "01", "00100", etc.

(iii) [(00+11)+(01+10)(00+11)∗(01+10)]∗[(00 + 11) + (01 + 10)(00 + 11)^* (01 +

10)]^*[(00+11)+(01+10)(00+11)∗(01+10)]∗

• This regular expression represents strings that:

o Can be formed by concatenating any number of occurrences of the following:
▪ A "00" or "11" from the first part, or
▪ A string formed by the combination of "01" or "10" followed by any number
of repetitions of "00" or "11", and ending with "01" or "10".

This expression allows strings like "", "00", "11", "010", "101", "0010", etc.

4. Construct finite automata equivalent to the following regular expressions:

(i) Regular Expression: 10+(0+11)0∗110 + (0 + 11) 0^* 110+(0+11)0∗1

The finite automaton will have the following transitions:

• Start state q0q_0q0:

o Transition on '1' to q1q_1q1 (accepts "10").
o Transition on '0' to q2q_2q2.
• From q2q_2q2, loop on '0' and move to state q3q_3q3 on '1' (accepts "011", "0001", ...).
• Accepting state: q1,q3q_1, q_3q1,q3.
(ii) Regular Expression: (a+bb)∗aa(a + bb)^* aa(a+bb)∗aa

The automaton will have:

• Start state loops on 'a' or 'bb'.

• Final state transitions to "aa".

(iii) Regular Expression: (ab+ba)∗a(ab∗)∗(ab + ba)^* a (ab*)^*(ab+ba)∗a(ab∗)∗

Construct an NFA with the following states:

• Start state that loops on "ab" or "ba".

• State for the final 'a'.
• Another state for "ab*" after the "a".

5. Check whether the following languages are regular:

(ii) Language L={0n∣n is prime}L = \{ 0^n \mid n \text{ is prime} \}L={0n∣n is prime}

This language is not regular. A standard method to prove this is by using the Pumping
Lemma. According to the Pumping Lemma, if a language is regular, there exists a pumping
length ppp. However, for this language, it is impossible to decompose strings of prime
lengths into three parts where the middle part can be pumped while keeping the string in the
language. The number of '0's in the string must always be prime, and pumping will break this
property.

6. Find L=L1∩L2L = L_1 \cap L_2L=L1∩L2 where:

• L1L_1L1: All strings starting with 'a' and containing an even number of 'b's.
• L2L_2L2: All strings containing an odd number of 'b's.

To find L=L1∩L2L = L_1 \cap L_2L=L1∩L2, we need strings that:

• Start with 'a'.

• Have an even number of 'b's overall, and also an odd number of 'b's.

This results in the empty language, as no string can have both an even and odd number of 'b's
simultaneously.

7. How to apply pumping lemma to prove certain languages are non-regular?

To apply the Pumping Lemma to prove that a language LLL is non-regular:

1. Assume that LLL is regular.

2. Let ppp be the pumping length for LLL (as per the Pumping Lemma).
3. Choose a string sss in LLL such that ∣s∣≥p|s| \geq p∣s∣≥p.
4. Split sss into three parts: s=xyzs = xyzs=xyz, where:
o ∣xy∣≤p|xy| \leq p∣xy∣≤p,
o ∣y∣>0|y| > 0∣y∣>0,
o xyiz∈Lx y^i z \in Lxyiz∈L for all i≥0i \geq 0i≥0.
 5. Show that no matter how you pump yyy (repeat it any number of times), the resulting string
will not belong to LLL, leading to a contradiction. This proves LLL is non-regular.

8. Construct NFA for regular expression 10∗+0∗1 0^* + 0^*10∗+0∗.

The NFA can be constructed as follows:

• Start state that transitions on '1' to a new state.

• From the second state, transition on '0' (loop on 0).
• Alternatively, from the start state, transition on '0' and loop on '0'.
• Accepting states are both states after reading '1' or '0' (accepts strings like "1", "000",
"1000", etc.).

1. What is grammar? Explain with example.

Grammar is a formal system that defines the structure of a language by specifying a set of
rules, called production rules, that describe how symbols can be combined to form valid
strings in the language. It consists of:

• Terminals (alphabet): The basic symbols from which strings are formed.
• Non-terminals: Symbols used to define patterns for strings, which can be further expanded.
• Start symbol: A special non-terminal from which derivation begins.
• Production rules: These describe how non-terminals can be replaced by combinations of
terminals and other non-terminals.

Example:

For the grammar G=(V,T,P,S)G = (V, T, P, S)G=(V,T,P,S), where:

• V={S,A}V = \{S, A\}V={S,A} (non-terminals),

• T={a,b}T = \{a, b\}T={a,b} (terminals),
• PPP consists of production rules:
1. S→aAS \rightarrow aAS→aA
2. A→bA \rightarrow bA→b
• Start symbol: SSS

This grammar generates the string "ab".

2. With the help of example describe derivation.

Derivation is the process of generating a string in the language from the start symbol of a
grammar by applying production rules in a step-by-step manner.

Example:

For the grammar:

• S→aAS \rightarrow aAS→aA

• A→bA \rightarrow bA→b
The derivation of the string "ab" from the start symbol SSS is as follows:

1. S→aAS \rightarrow aAS→aA (using S→aAS \rightarrow aAS→aA)

2. aA→abaA \rightarrow abaA→ab (using A→bA \rightarrow bA→b)

Thus, the derivation for "ab" is S⇒aA⇒abS \Rightarrow aA \Rightarrow abS⇒aA⇒ab.

3. What is reduction? Define it. Also explain with example.

Reduction is the reverse of derivation, where a string is reduced step by step to the start
symbol by applying production rules in reverse. It is a process of simplifying a string by
replacing its components with non-terminals according to the production rules.

Example:

Consider the string "ab" and the grammar:

• S→aAS \rightarrow aAS→aA

• A→bA \rightarrow bA→b

To reduce "ab" back to the start symbol SSS:

1. Start with the string "ab".

2. Apply the reverse of A→bA \rightarrow bA→b, replacing "b" with AAA: ab→aAab
\rightarrow aAab→aA.
3. Then apply the reverse of S→aAS \rightarrow aAS→aA, replacing "aA" with SSS: aA→SaA
\rightarrow SaA→S.

Thus, the reduction of "ab" is ab⇒aA⇒Sab \Rightarrow aA \Rightarrow Sab⇒aA⇒S.

4. Construct the CFG accepting each of the following sets:

(i) Set: {anbmambn∣m,n≥1}\{ a^n b^m a^m b^n \mid m, n \geq 1 \}{anbmambn∣m,n≥1}

CFG:

• S→aSb∣aAbS \rightarrow aSb \mid aAbS→aSb∣aAb

• A→aAb∣ϵA \rightarrow aAb \mid \epsilonA→aAb∣ϵ

Explanation: The grammar generates strings with a balance of ana^nan and bnb^nbn at the
two ends, ensuring the structure is maintained.

(ii) Set: {anb2n∣n≥1}\{ a^n b^{2n} \mid n \geq 1 \}{anb2n∣n≥1}

CFG:

• S→aSb∣ab2S \rightarrow aSb \mid ab^2S→aSb∣ab2

Explanation: The grammar ensures that for every aaa there are exactly two bbb's following it.
(iii) Set: The set of all strings over {a,b}\{a, b\}{a,b} consisting of equal number of a's
and b's.

CFG:

• S→aSb∣bSa∣SS∣ϵS \rightarrow aSb \mid bSa \mid SS \mid \epsilonS→aSb∣bSa∣SS∣ϵ

Explanation: The grammar generates strings where each aaa is paired with a corresponding
bbb, and it can recursively generate substrings with equal numbers of aaa's and bbb's.

5. Consider the following grammar:

S → aB | bA
A → aS | bAA | a
B → bS | aBB | b

For the string "aaabbabbba", find:

• (i) Leftmost derivation

• (ii) Rightmost derivation
• (iii) Parse tree

(i) Leftmost derivation:

Starting from SSS:

1. S→aBS \rightarrow aBS→aB (using S→aBS \rightarrow aBS→aB)

2. B→bSB \rightarrow bSB→bS (using B→bSB \rightarrow bSB→bS)
3. S→aBS \rightarrow aBS→aB (using S→aBS \rightarrow aBS→aB)
4. B→bSB \rightarrow bSB→bS (using B→bSB \rightarrow bSB→bS)
5. S→bAS \rightarrow bAS→bA (using S→bAS \rightarrow bAS→bA)
6. A→bAAA \rightarrow bAAA→bAA (using A→bAAA \rightarrow bAAA→bAA)
7. A→aSA \rightarrow aSA→aS (using A→aSA \rightarrow aSA→aS)
8. S→aBS \rightarrow aBS→aB (using S→aBS \rightarrow aBS→aB)
9. B→bSB \rightarrow bSB→bS (using B→bSB \rightarrow bSB→bS)
10. S→bAS \rightarrow bAS→bA (using S→bAS \rightarrow bAS→bA)
11. A→aA \rightarrow aA→a (using A→aA \rightarrow aA→a)

Thus, the leftmost derivation is:

S⇒aB⇒abS⇒abaB⇒ababS⇒ababaB⇒abababS⇒ababababA⇒ababababaS \Rightarrow aB
\Rightarrow abS \Rightarrow abaB \Rightarrow ababS \Rightarrow ababaB \Rightarrow
abababS \Rightarrow ababababA \Rightarrow
ababababaS⇒aB⇒abS⇒abaB⇒ababS⇒ababaB⇒abababS⇒ababababA⇒ababababa.

(ii) Rightmost derivation:

Starting from SSS:

1. S→aBS \rightarrow aBS→aB (using S→aBS \rightarrow aBS→aB)

 2. B→bSB \rightarrow bSB→bS (using B→bSB \rightarrow bSB→bS)
3. S→bAS \rightarrow bAS→bA (using S→bAS \rightarrow bAS→bA)
4. A→aSA \rightarrow aSA→aS (using A→aSA \rightarrow aSA→aS)
5. S→bAS \rightarrow bAS→bA (using S→bAS \rightarrow bAS→bA)
6. A→bAAA \rightarrow bAAA→bAA (using A→bAAA \rightarrow bAAA→bAA)
7. A→aSA \rightarrow aSA→aS (using A→aSA \rightarrow aSA→aS)
8. S→aBS \rightarrow aBS→aB (using S→aBS \rightarrow aBS→aB)
9. B→bSB \rightarrow bSB→bS (using B→bSB \rightarrow bSB→bS)
10. S→bAS \rightarrow bAS→bA (using S→bAS \rightarrow bAS→bA)
11. A→aA \rightarrow aA→a (using A→aA \rightarrow aA→a)

Thus, the rightmost derivation is:

S⇒aB⇒abS⇒abS⇒abSb⇒abSbA⇒abSbAS \Rightarrow aB \Rightarrow abS \Rightarrow

abS \Rightarrow abSb \Rightarrow abSbA \Rightarrow
abSbAS⇒aB⇒abS⇒abS⇒abSb⇒abSbA⇒abSbA.

(iii) Parse Tree:

The parse tree for the string "aaabbabbba" is a graphical representation of the derivation
steps, where each node corresponds to a non-terminal, and each branch corresponds to a
production rule applied.

6. Show that the following CFGs are ambiguous:

(i) CFG:

S → a | abSb | aAb
A → bS | aAAb

Proof of Ambiguity: The grammar is ambiguous if there is more than one leftmost or
rightmost derivation for a string.

For example, for the string "ababb", we can derive it in two different ways:

• One derivation can be S→abSbS \rightarrow abSbS→abSb and S→aAbS \rightarrow

aAbS→aAb for different intermediate steps.
• Another derivation can be S→abSbS \rightarrow abSbS→abSb and A→aAbA \rightarrow
aAbA→aAb.

Thus, this grammar is ambiguous.

(ii) CFG:

S → S + S | S * S | (S) | a

Proof of Ambiguity: For the string "a + a * a", we can derive it in multiple ways:

1. S→S+S→a+S→a+a∗aS \rightarrow S + S \rightarrow a + S \rightarrow a + a *

aS→S+S→a+S→a+a∗a
 2. S→S∗S→a∗S→a∗a→a+a∗aS \rightarrow S * S \rightarrow a * S \rightarrow a * a \rightarrow
a + a * aS→S∗S→a∗S→a∗a→a+a∗a

Thus, this grammar is also ambiguous.

7. Find CFGs with no useless symbols equivalent to the given CFG:

Given CFG:

css
Copy code
S → AB | CA
A → a
B → BC | AB
C → aB | b

Step 1: Remove unreachable symbols

• Start symbol SSS is reachable because it can be derived.

• From S→ABS → ABS→AB and S→CAS → CAS→CA, symbols AAA, BBB, and
CCC are reachable from SSS.
• AAA is reachable directly, BBB is reachable from S→ABS → ABS→AB and CCC is
reachable from S→CAS → CAS→CA.
• All symbols are reachable.

Step 2: Remove non-generating symbols

• For a non-generating symbol, no derivation leads to a terminal string.

• A→aA → aA→a generates a terminal string, so AAA is generating.
• B→BC∣ABB → BC | ABB→BC∣AB contains non-terminals BBB and CCC, but we
need to check if the production rules can eventually lead to terminal strings.
• C→aB∣bC → aB | bC→aB∣b generates a terminal string since C→bC → bC→b
directly generates terminal string bbb.

All symbols are generating, so no non-generating symbols are present.

Step 3: Remove useless symbols

Since all symbols are reachable and generating, the given grammar already has no useless
symbols. Hence, the equivalent grammar with no useless symbols is:

css
Copy code
S → AB | CA
A → a
B → BC | AB
C → aB | b

8. Design equivalent CFG without unit productions for the following CFGs:

Given CFG:
css
Copy code
S → 0A | 1B
A → S
B → 1B | 1

Step 1: Remove unit productions

Unit production is of the form X→YX → YX→Y, where both XXX and YYY are non-
terminals.

• A→SA → SA→S is a unit production.

We replace the unit production by substituting the rules of SSS into AAA:

• S→0A∣1BS → 0A | 1BS→0A∣1B
• A→0A∣1BA → 0A | 1BA→0A∣1B

Thus, we replace A→SA → SA→S by:

css
Copy code
A → 0A | 1B

So, the equivalent grammar without unit productions is:

css
Copy code
S → 0A | 1B
A → 0A | 1B
B → 1B | 1

9. Convert the following CFG into CNF:

Given CFG:

css
Copy code
S → abAB | bAda
A → baB | a
B → CAb | Bb

Step 1: Eliminate terminals from mixed productions

• For S→abABS → abABS→abAB, introduce new non-terminals to represent terminal

pairs: Let X1→abX_1 → abX1→ab, then: S→X1ABS → X_1ABS→X1AB
• For S→bAdaS → bAdaS→bAda, introduce new non-terminals for terminal symbols:
Let X2→bX_2 → bX2→b and X3→aX_3 → aX3→a, then: S→X2ADX3S →
X_2ADX_3S→X2ADX3

Step 2: Eliminate productions where a non-terminal appears on the right side more
than twice
 • Replace A→baBA → baBA→baB with A→X4BA → X_4BA→X4B where
X4→baX_4 → baX4→ba.
• Replace B→CAbB → CAbB→CAb with B→CAX1B → CAX_1B→CAX1, where
X1→bX_1 → bX1→b.

Step 3: Ensure productions are in CNF (each production has either one non-terminal or
two non-terminals)

Final CNF (Chomsky Normal Form) will be:

css
Copy code
S → X_1AB | X_2ADX_3
A → X_4B | a
B → CAX_1 | Bb
X_1 → ab
X_2 → b
X_3 → a
X_4 → ba

10. Write a short note on: Simplification of CFG.

Simplification of CFG involves removing unnecessary parts of the grammar that do not
contribute to the generation of valid strings. The main steps for simplification are:

1. Remove unreachable symbols: Any non-terminal that cannot be reached from the
start symbol should be removed.
2. Remove useless symbols: Non-terminals that cannot derive a terminal string should
be removed.
3. Eliminate unit productions: Productions of the form A→BA \rightarrow BA→B
where both AAA and BBB are non-terminals should be replaced by the productions
of BBB.
4. Eliminate useless rules: Productions that do not generate terminal strings or lead to
valid derivations should be removed.

11. Describe Chomsky hierarchy with four types of grammars.

The Chomsky hierarchy classifies formal grammars into four types based on their
generative power:

1. Type 0 (Recursively enumerable languages): These grammars are unrestricted, with

production rules of the form α→β\alpha \rightarrow \betaα→β, where α\alphaα and
β\betaβ can be any strings of symbols.
o Example: All languages that can be generated by a Turing machine.
2. Type 1 (Context-sensitive languages): These grammars have production rules of the
form αAβ→αγβ\alpha A \beta \rightarrow \alpha \gamma \betaαAβ→αγβ, where
AAA is a non-terminal and γ\gammaγ is a non-empty string. The length of the string
on the left-hand side cannot be smaller than the right-hand side.
o Example: The language {anbncn∣n≥1}\{a^n b^n c^n | n \geq 1
\}{anbncn∣n≥1}.
 3. Type 2 (Context-free languages): These grammars have production rules of the form
A→γA \rightarrow \gammaA→γ, where AAA is a non-terminal and γ\gammaγ can be
any string of terminals and non-terminals.
o Example: The language of balanced parentheses.
4. Type 3 (Regular languages): These grammars have production rules of the form
A→aBA \rightarrow aBA→aB or A→aA \rightarrow aA→a, where AAA is a non-
terminal and aaa is a terminal.
o Example: The language {anbn∣n≥1}\{a^n b^n | n \geq 1 \}{anbn∣n≥1}.

12. What is ambiguous grammar? Explain its concept with example.

Ambiguous grammar is a grammar for which there exists at least one string that can be
derived in more than one way, resulting in multiple parse trees or derivations.

Example:

Consider the grammar:

css
Copy code
S → aS | bS | a

For the string "aa", we have two possible derivations:

1. S⇒aS⇒aaS \Rightarrow aS \Rightarrow aaS⇒aS⇒aa

2. S⇒a⇒aaS \Rightarrow a \Rightarrow aaS⇒a⇒aa

Thus, the grammar is ambiguous because there are multiple derivations for the same string.

13. How to construct a regular grammar equivalent to a given DFA?

To construct a regular grammar from a DFA:

1. States of the DFA become non-terminals in the grammar.

2. Transitions between states are represented by production rules, where:
o For a transition from state qiq_iqi to state qjq_jqj on symbol aaa, the
production is qi→aqjq_i \rightarrow a q_jqi→aqj.
3. Final states of the DFA become the productions that lead to terminal strings. If state
qfq_fqf is final, then add a production qf→ϵq_f \rightarrow \epsilonqf→ϵ.
4. Start state is the start non-terminal in the grammar.

14. What is normal form? Explain Greibach Normal Form (GNF) and
Chomsky Normal Form (CNF) with example. Also compare them.

Normal forms are standard forms for grammars where all production rules follow a specific
pattern.

• Chomsky Normal Form (CNF): A CFG is in CNF if every production is of the

form:
o A→BCA \rightarrow BCA→BC (two non-terminals) or
 o A→aA \rightarrow aA→a (a terminal).
o No ϵ\epsilonϵ-productions or unit productions.
o Example:

css
Copy code
S → AB | a
A → a
B → b

• Greibach Normal Form (GNF): A CFG is in GNF if every production is of the

form:
o A→aαA \rightarrow a \alphaA→aα where aaa is a terminal and α\alphaα is a
string of non-terminals.
o Example:

css
Copy code
S → aA | bB
A → a | bS
B → b

Comparison:

• CNF is more restrictive than GNF as it only allows two non-terminals or a terminal in
each production.
• GNF can generate more types of languages but may require more steps to convert.

15. Convert the following grammar to GNF:

Given CFG:

css
Copy code
S → AA | a
A → SS | b

Step 1: Apply GNF rules. Each production must have a terminal followed by non-terminals.

• S→AAS → AAS→AA becomes S→aAS → aAS→aA (by GNF rules).

• A→SSA → SSA→SS becomes A→bA → bA→b.

16. Consider the following grammar:

css
Copy code
S → AB | aD | a
A → a
D → aD | aDD

Remove useless symbols:

• AAA is reachable and generates terminal strings, so it remains.

 • SSS is reachable and generates terminal strings, so it remains.
• DDD is reachable and generates terminal strings, so it remains.

Thus, no symbols are useless in this grammar.

17. Write a short note on Chomsky's hierarchy.

Chomsky's hierarchy classifies formal grammars into four types:

1. Type 0 (Recursively enumerable languages): No restrictions on the production

rules.
2. Type 1 (Context-sensitive languages): Rules have a length constraint, and the length
of the string on the left-hand side is greater than or equal to the right-hand side.
3. Type 2 (Context-free languages): Rules have a single non-terminal on the left-hand
side and any combination of terminals and non-terminals on the right-hand side.
4. Type 3 (Regular languages): Rules only have one non-terminal on the left side and a
terminal or non-terminal on the right.

This hierarchy helps understand the complexity of languages and automata that can accept
them.

1. What is PDA? Explain with the help of diagram.

A Pushdown Automaton (PDA) is a type of automaton that uses a stack as an auxiliary

memory to recognize context-free languages (CFLs). Unlike a finite automaton (FA), which
has no extra memory, a PDA can store an unbounded number of symbols using its stack. This
allows PDAs to handle languages with recursive or nested structures, such as balanced
parentheses or matched pairs.

Components of a PDA:

• States (Q): A finite set of states the machine can be in.

• Input Alphabet (Σ): The set of symbols the PDA reads from the input.
• Stack Alphabet (Γ): The set of symbols that can be pushed or popped from the stack.
• Transition Function (δ): A set of rules that describe how the PDA transitions between states
based on the current state, input symbol, and the top of the stack.
• Start State (q₀): The state in which the PDA starts.
• Start Stack Symbol (Z₀): The initial symbol placed on the stack.
• Accepting States (F): The set of states in which the PDA accepts the input.

The PDA works by reading the input symbol, pushing or popping symbols from the stack,
and changing states according to the transition function.

Diagram:

lua
Copy code
+---------------------+
| Input: a, Stack: Z |
| δ(q0, a, Z) → (q1, Z) |
 +---------------------+
|
v
+---------------------+
| Input: ε, Stack: Z |
| δ(q1, ε, Z) → (q2, Z) |
+---------------------+
|
v
+---------------------+
| Input: b, Stack: Z |
| δ(q2, b, Z) → (q2, Z) |
+---------------------+
|
v
Accepting state (q2) if stack is empty.

2. How to construct a PDA using empty stack and final state methods?

A Pushdown Automaton (PDA) can accept languages in two ways: by empty stack or by
final state.

• Empty Stack Acceptance: In this method, the PDA accepts the input if, after
processing all input symbols, the stack is empty, regardless of the current state. This is
particularly useful when the language involves matching pairs or nested structures,
like balanced parentheses.
• Final State Acceptance: In this method, the PDA accepts the input if, after
processing the input, the PDA reaches an accepting state, regardless of the contents of
the stack. This is more typical of deterministic PDAs.

Construction using Empty Stack Method:

1. Create a PDA with an initial state q0q_0q0.

2. Transition between states based on input, while pushing and popping symbols from the
stack.
3. If, after consuming all input, the stack is empty, the PDA will accept the string.

Construction using Final State Method:

1. Construct a PDA that processes the input symbols while manipulating the stack.
2. The PDA transitions to an accepting state when all the input is consumed.

3. Give an equivalent PDA for the following CFG:

S→ABS \rightarrow ABS→AB A→BB ∣ aA \rightarrow BB \,|\, aA→BB∣a B→AB ∣ a ∣ bB \rightarrow AB

\,|\, a \,|\, bB→AB∣a∣b

PDA Construction: The PDA will use the stack to simulate the derivation of this grammar.
Here's the PDA:

• States (Q): {q0,q1}\{ q_0, q_1 \}{q0,q1}

• Input Alphabet (Σ): {a,b}\{a, b\}{a,b}
• Stack Alphabet (Γ): {A,B,Z0}\{A, B, Z_0\}{A,B,Z0}, where Z0Z_0Z0 is the initial stack symbol.
 • Start State: q0q_0q0
• Accepting States (F): {q1}\{ q_1 \}{q1}
• Start Stack Symbol: Z0Z_0Z0
• Transition Function (δ):
o δ(q0,ϵ,Z0)=(q0,ABZ0)δ(q_0, \epsilon, Z_0) = (q_0, ABZ_0)δ(q0,ϵ,Z0)=(q0,ABZ0) —
push AAA and BBB to simulate the production S→ABS \rightarrow ABS→AB.
o δ(q0,a,A)=(q0,a)δ(q_0, a, A) = (q_0, a)δ(q0,a,A)=(q0,a) — transition for A→aA
\rightarrow aA→a.
o δ(q0,b,B)=(q0,b)δ(q_0, b, B) = (q_0, b)δ(q0,b,B)=(q0,b) — transition for B→bB
\rightarrow bB→b.
o δ(q0,a,B)=(q0,a)δ(q_0, a, B) = (q_0, a)δ(q0,a,B)=(q0,a) — transition for B→aB
\rightarrow aB→a.
o δ(q0,b,A)=(q0,b)δ(q_0, b, A) = (q_0, b)δ(q0,b,A)=(q0,b) — transition for A→bA
\rightarrow bA→b.
o δ(q0,ϵ,Z0)=(q1,Z0)δ(q_0, \epsilon, Z_0) = (q_1, Z_0)δ(q0,ϵ,Z0)=(q1,Z0) — when the
input is exhausted, transition to the accepting state if the stack is empty.

4. Construct a PDA for the following languages:

(i) L={anb2n∣n≥1}L = \{ a^n b^{2n} | n \geq 1 \}L={anb2n∣n≥1}

This language consists of strings where the number of b's is exactly double the number of a's.
To construct the PDA:

1. States (Q): {q0,q1,q2}\{q_0, q_1, q_2\}{q0,q1,q2}

2. Input Alphabet (Σ): {a,b}\{a, b\}{a,b}
3. Stack Alphabet (Γ): {A,Z0}\{A, Z_0\}{A,Z0}
4. Start State: q0q_0q0
5. Accepting States: q2q_2q2
6. Transition Function (δ):
o δ(q0,a,Z0)=(q0,AZ0)δ(q_0, a, Z_0) = (q_0, A Z_0)δ(q0,a,Z0)=(q0,AZ0) — push A for
each a read.
o δ(q0,b,A)=(q1,A)δ(q_0, b, A) = (q_1, A)δ(q0,b,A)=(q1,A) — read two b's for each A in
the stack.
o δ(q1,b,A)=(q1,A)δ(q_1, b, A) = (q_1, A)δ(q1,b,A)=(q1,A) — continue reading b's and
popping A from the stack.
o δ(q1,ϵ,Z0)=(q2,Z0)δ(q_1, \epsilon, Z_0) = (q_2, Z_0)δ(q1,ϵ,Z0)=(q2,Z0) — when stack
is empty, transition to the accepting state.

(ii) L={0n12n+1∣n≥1}L = \{ 0^n 1^{2n+1} | n \geq 1 \}L={0n12n+1∣n≥1}

This language consists of strings with n 0's followed by 2n+1 1's. The PDA construction is
similar to the one above, but this time, we need to count an additional 1.

(iii) L={anbman∣m,n≥1}L = \{ a^n b^m a^n | m, n \geq 1 \}L={anbman∣m,n≥1}

This language contains strings with a's on both ends and b's in between. The PDA will push
and pop symbols from the stack to match the number of a's before and after the b's.

5. Write the formal definition of DPDA and NPDA.

 • DPDA (Deterministic Pushdown Automaton): A DPDA is a PDA where for each
state, input symbol, and stack symbol, there is at most one transition. This makes the
machine deterministic in nature.
• NPDA (Non-deterministic Pushdown Automaton): An NPDA is a PDA where for
a given state, input symbol, and stack symbol, there may be multiple transitions. This
allows the machine to non-deterministically explore multiple computational paths.

6. Convert the following CFG into PDA:

S→1S∣1S0S∣1S \rightarrow 1S | 1S0S | 1S→1S∣1S0S∣1

To convert this CFG into a PDA, you would follow the same procedure as the previous CFG
examples, using the stack to simulate the derivations of the grammar. Here’s the PDA
structure:

• States (Q): {q0,q1}\{q_0, q_1\}{q0,q1}

• Input Alphabet (Σ): {1,0}\{1, 0\}{1,0}
• Stack Alphabet (Γ): {S,Z0}\{S, Z_0\}{S,Z0}
• Start State: q0q_0q0
• Accepting State: q1q_1q1
• Transition Function (δ):
o δ(q0,1,Z0)=(q0,SZ0)δ(q_0, 1, Z_0) = (q_0, SZ_0)δ(q0,1,Z0)=(q0,SZ0) — push S on
reading 1.
o δ(q0,1,S)=(q0,SS)δ(q_0, 1, S) = (q_0, SS)δ(q0,1,S)=(q0,SS) — recursively push S for 1.
o δ(q0,0,S)=(q0,0)δ(q_0, 0, S) = (q_0, 0)δ(q0,0,S)=(q0,0) — consume 0 and pop S from
the stack.
o δ(q0,ϵ,Z0)=(q1,Z0)δ(q_0, \epsilon, Z_0) = (q_1, Z_0)δ(q0,ϵ,Z0)=(q1,Z0) — accepting
when input is exhausted.

7. Write a mapping of d in PDA.

The mapping function for a PDA is typically the transition function δ\deltaδ, which takes a
tuple of state, input symbol, and stack symbol, and returns a new state and stack
configuration. The function ddd can be defined as:

d(q,a,X)→(q′,Y)d(q, a, X) \rightarrow (q', Y)d(q,a,X)→(q′,Y)

where:

• qqq is the current state,

• aaa is the current input symbol,
• XXX is the top symbol of the stack,
• q′q'q′ is the next state,
• YYY is the new stack configuration (which could involve pushing, popping, or no operation).

8. Construct PDA that accepts language S→aS∣aSbS∣aS \rightarrow aS | aSbS

| aS→aS∣aSbS∣a:

This language consists of strings of the form anbna^n b^nanbn, with a's and b's nested in the
middle. The PDA will push a's onto the stack and then pop them when reading b's.
 • States (Q): {q0,q1}\{q_0, q_1\}{q0,q1}
• Input Alphabet (Σ): {a,b}\{a, b\}{a,b}
• Stack Alphabet (Γ): {S,Z0}\{S, Z_0\}{S,Z0}
• Start State: q0q_0q0
• Accepting State: q1q_1q1
• Transition Function (δ):
o δ(q0,a,Z0)=(q0,aZ0)δ(q_0, a, Z_0) = (q_0, aZ_0)δ(q0,a,Z0)=(q0,aZ0) — push a on
stack for each a.
o δ(q0,b,a)=(q0,ϵ)δ(q_0, b, a) = (q_0, \epsilon)δ(q0,b,a)=(q0,ϵ) — pop a on reading b.
o δ(q0,ϵ,Z0)=(q1,Z0)δ(q_0, \epsilon, Z_0) = (q_1, Z_0)δ(q0,ϵ,Z0)=(q1,Z0) — accept
when input is exhausted.

1. What is TM? How it works? Explain its model diagrammatically.

A Turing Machine (TM) is a theoretical computational model used to define algorithmic

processes. It is a formal model of computation that can simulate any computer algorithm. It
consists of the following components:

• Tape: An infinite sequence of cells, each of which holds a symbol from a finite alphabet.
• Tape Head: A read/write head that can move left or right along the tape, reading or writing
symbols in the tape cells.
• Finite State Control: A finite set of states that the machine can be in, including a start state
and one or more accepting/rejecting states.
• Transition Function: A set of rules that determine the machine's next state based on the
current state and symbol under the tape head.

Working:

The Turing machine starts in the initial state and reads the input string from the tape. Based
on the current state and the symbol being read, the transition function dictates whether to
write a symbol, move the tape head, and transition to a new state. This continues until the
machine reaches a halting state (either accept or reject).

Diagram:
mathematica
Copy code
[Start State] --> [Transition Rules] --> [Tape Head]
| |
Read Symbol Write Symbol
|
Move Tape Head

2. What is LBA? Describe in detail.

A Linear Bounded Automaton (LBA) is a restricted type of Turing machine where the tape
is limited to a length that is linearly proportional to the size of the input. Unlike a standard
Turing machine that has infinite tape, an LBA operates with a tape that can only hold a finite
amount of information relative to the input length.
An LBA is defined by the following:

• Finite Set of States: Like a Turing machine, it has a set of states.

• Tape: The tape is finite and bounded by the length of the input, meaning it cannot use
unlimited memory.
• Transition Function: Similar to Turing machines, the LBA follows a set of transition rules
based on its current state and tape symbol.

LBAs can only recognize context-sensitive languages, which are a subset of the languages
recognized by Turing machines. This limitation comes from the tape size restriction, which
makes it less powerful than a full Turing machine.

3. Construct a TM to accept the following languages:

(i) {0^n 1^n 0^n | n ≥ 1}

A Turing machine for this language would need to perform the following steps:

1. Scan the first 0, move right to the first 1.

2. Replace the first 0 with X and the first 1 with Y, and move the head back to the leftmost 0 in
the sequence.
3. Repeat this process, ensuring that each 0 is paired with a 1 and the remaining part of the
string is checked.
4. After all 0s and 1s are matched, check if the remaining 0s are also correctly placed.

(ii) {ww^R | w is in (0 + 1)*}

1. The TM starts at the leftmost position and reads the first symbol of the string (either 0 or 1).
2. The machine writes a mark (X or Y) on the first symbol and searches for its mirror image on
the other side (i.e., the reverse of the string).
3. The process is repeated until the entire string has been matched, ensuring the string is a
palindrome.

4. Design a TM to perform proper subtraction of two unary numbers.

In unary, a number is represented by repeated symbols (e.g., 111 for 3). To perform
subtraction on two unary numbers:

1. The machine reads the first unary number (let’s say as), moves to the second unary number
(bs).
2. For each a in the first number, it attempts to "pair" it with a b in the second number.
3. If there are more as than bs, the TM will leave the remaining as and accept the result as a
non-negative integer. If there are fewer as, it will reject the input.
4. After all possible pairs have been removed, the remaining as represent the result of the
subtraction.

5. Design a TM to check palindrome.

A Turing machine that checks for palindromes follows these steps:

 1. The machine starts by reading the first symbol of the string and moves to the last symbol.
2. It compares the first and last symbols. If they match, the machine marks both as checked
(using X or Y) and moves inward.
3. This process continues, checking the outermost symbols until the middle of the string is
reached.
4. If any mismatch is found, the machine rejects the string; otherwise, it accepts the string.

6. Construct a TM which recognizes a language which contains equal number

of a's and b's.

The Turing machine can recognize this language as follows:

1. The TM starts by scanning the first a and marks it with X.

2. It then searches for a corresponding b to mark with Y. If found, the machine returns to the
leftmost unmarked symbol.
3. This process repeats until all as and bs are matched. If an unequal number of as and bs are
encountered, the machine rejects.
4. If all symbols are matched and the tape is empty, the machine accepts the input.

7. With the help of a diagram, describe the basic model of LBA.

The basic model of LBA is similar to a Turing machine but with the restriction that the tape
can only be used within a bounded region proportional to the input size.

css
Copy code
|---- Tape ----|
|
[Input String]
|
[State] ---> [Transition Rules] ---> [Tape Head Movement]

In this model, the LBA can only move within the bounds of the input length and operates
using the same rules as a Turing machine but with the restriction of tape size.

8. Write a short note on: Language accepted by TM.

A Turing machine can accept a language if, for every string in the language, the machine
reaches an accepting state after processing the string. A Turing machine can recognize
recursively enumerable languages (Type-0 languages). These are languages for which a
Turing machine will eventually halt and accept the string if it belongs to the language;
otherwise, it may not halt (in the case of strings not in the language).

9. What is Non-deterministic TM? Explain with an example.

A non-deterministic Turing machine (NDTM) is a Turing machine where, for some states
and input symbols, the machine has more than one possible transition (i.e., it can make a
choice between several paths). Unlike deterministic TMs, where the machine's next move is
completely determined by its current state and symbol, in NDTMs, the machine can explore
multiple computation paths simultaneously.
Example: For the input string "a", the machine could have two possible transitions:

1. Move right and stay in the same state.

2. Write a symbol and move left.

This non-deterministic behavior allows the machine to perform multiple actions and explore
different possibilities.

10. With the help of an example, explain Multi-Tape TM.

A Multi-Tape Turing Machine has multiple tapes, each with its own read/write head. The
machine can operate on all tapes simultaneously.

Example: For a language where the machine needs to copy a string from one tape to another,
the machine can:

1. Read the first symbol from tape 1 and write it to tape 2.

2. Move both heads right and repeat the process.

While a single-tape Turing machine would require additional steps to simulate the same
process, a multi-tape machine can perform it much more efficiently.

11. Construct a TM for a language L, where L = {a^m + n b^m c^n | m, n ≥

1}.

1. The machine first checks for as and marks them, moving to the bs.
2. For each a on the tape, the machine matches it with a b and then moves on to the cs.
3. After matching all bs with as, the machine continues matching cs with bs.
4. If it successfully matches all symbols and moves to an accepting state, it accepts the input.

12. Construct a TM for a language L, where L = {a^m b^n | n > m, m > 1}.

1. The machine starts by reading as and marking them.

2. It then reads bs and checks that the number of bs is greater than the number of as.
3. If the condition n > m is met, the machine accepts the string; otherwise, it rejects.

This ensures that the number of bs is always greater than the number of as and that m > 1.