2025 question paper

FORMAL LANGUAGE & AUTOMATA THEORY

28 questions

1. Q1a. A language is said to be recursively enumerable if it is accepted by a (i) DFA (ii) Turing Machine (iii) PDA (iv) Linear Bounded Automaton20252m

   Module 4: Turing Machines (TM)

   A language is said to be recursively enumerable if it is accepted by a

   (i) DFA
   (ii) Turing Machine
   (iii) PDA
   (iv) Linear Bounded Automaton

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer

   Correct Option: (ii) Turing Machine

   Explanation

   A language $L$ is called Recursively Enumerable (RE) iff there exists a Turing Machine $M$ such that $L = L(M)$, i.e., $M$ halts and accepts exactly the strings in $L$. On strings not in $L$, $M$ may either reject or loop forever. This is the most general language class in the Chomsky hierarchy (Type-0).

   Why other options are incorrect

   • (i) DFA : Accepts Regular languages (Type-3), strictly smaller than RE.
   • (iii) PDA : Accepts Context-Free Languages (Type-2), also properly contained in RE.
   • (iv) Linear Bounded Automaton (LBA) : Accepts Context-Sensitive Languages (Type-1), also a proper subset of RE.

   Hierarchy recall

   $$\text{REG} \subset \text{CFL} \subset \text{CSL} \subset \text{RE} \subset \text{ALL}$$

   • REG → DFA
   • CFL → PDA
   • CSL → LBA
   • RE → Turing Machine
   • Recursive → Decidable TM (always halts)

   Final Answer

   Hence, Recursively Enumerable Languages are exactly those accepted by Turing Machines. Correct answer is (ii) Turing Machine.

2. Q1b. Regular languages belong to which type in the Chomsky hierarchy? (i) Type-0 (ii) Type-2 (iii) Type-1 (iv) Type-320252m

   Module 1: Introduction & Regular Languages

   Regular languages belong to which type in the Chomsky hierarchy?

   (i) Type-0
   (ii) Type-2
   (iii) Type-1
   (iv) Type-3

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer

   Correct Option: (iv) Type-3

   Explanation

   Chomsky Hierarchy (Noam Chomsky, 1956)

   Type	Language Class	Grammar	Automaton
   Type-0	Recursively Enumerable	Unrestricted	Turing Machine
   Type-1	Context-Sensitive	Context-Sensitive	Linear Bounded Automaton
   Type-2	Context-Free	Context-Free	Pushdown Automata
   Type-3	Regular	Regular (Left/Right-linear)	Finite Automaton (DFA/NFA)

   Regular languages are the most restricted class, generated by:

   • Right-linear grammars: $A \rightarrow aB \mid a \mid \epsilon$
   • Left-linear grammars
   • Regular expressions

   and recognized by DFA/NFA/ε-NFA.

   They are strictly contained:
   $$\text{Type-3} \subset \text{Type-2} \subset \text{Type-1} \subset \text{Type-0}$$

   Final Answer

   Regular languages are Type-3 languages. Correct option (iv).

3. Q1c. Which of the following languages is NOT regular? (i) {a^n b^n | n \ge 0} (ii) {a, b}* (iii) Finite languages (iv) Languages accepted by DFA20252m

   Module 1: Introduction & Regular Languages

   Which of the following languages is NOT regular?

   (i) {$a^n b^n | n \ge 0$}
   (ii) {$a, b$}*
   (iii) Finite languages
   (iv) Languages accepted by DFA

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer

   Correct Option: (i) $\{a^n b^n \mid n \ge 0\}$

   Explanation

   • (ii) $\{a,b\}^*$ → Regular, regex $(a+b)^*$, DFA with 1 state.
   • (iii) Finite languages → Regular: any finite set is regular (union of finitely many strings).
   • (iv) Languages accepted by DFA → Definition of regular.
   • (i) $\{a^n b^n\}$ → Classic non-regular. Requires counting unbounded $n$ and matching $a$'s with $b$'s. Pumping Lemma: let $p$ be pumping length, $w = a^p b^p$, pumping $y$ (all $a$'s) breaks equality $|w|_a = |w|_b$.

   It is Context-Free (PDA can push $a$'s, pop for $b$'s) but not regular.

   Final Answer

   NOT regular is $\{a^n b^n\}$ → Option (i).

4. Q1d. Context-free languages are NOT closed under (i) Union (ii) Concatenation (iii) Intersection (iv) Kleene star20252m

   Module 2: Context-Free Languages (CFL) and PDA

   Context-free languages are NOT closed under

   (i) Union
   (ii) Concatenation
   (iii) Intersection
   (iv) Kleene star

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer

   Correct Option: (iii) Intersection

   Explanation

   Closure properties of Context-Free Languages (CFLs):

   Operation	Closed?
   Union $L_1 \cup L_2$	Yes – $S \rightarrow S_1 \mid S_2$
   Concatenation $L_1L_2$	Yes – $S \rightarrow S_1S_2$
   Kleene star $L^*$	Yes – $S \rightarrow SS_1 \mid \epsilon$
   Intersection $L_1 \cap L_2$	No
   Complement $\overline{L}$	No

   Counterexample for intersection:
   $L_1 = \{a^n b^n c^m \mid n,m\ge0\}$ (CFL), $L_2 = \{a^m b^n c^n \mid n,m\ge0\}$ (CFL)
   $L_1 \cap L_2 = \{a^n b^n c^n\}$ which is not CFL (pumping lemma).

   Since De Morgan: $L_1 \cap L_2 = \overline{\,\overline{L_1}\cup\overline{L_2}\,}$, non-closure under intersection implies non-closure under complement.

   Final Answer

   CFLs are NOT closed under Intersection → Option (iii).

5. Q1e. Which production is not allowed in a CSG? (i) AB \rightarrow BA (ii) A \rightarrow \epsilon (iii) A \rightarrow a (iv) a B \rightarrow a b20252m

   Module 3: Context-Sensitive Languages

   Which production is not allowed in a CSG?

   (i) $AB \rightarrow BA$
   (ii) $A \rightarrow \epsilon$
   (iii) $A \rightarrow a$
   (iv) $a B \rightarrow a b$

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer

   Correct Option: (ii) $A \rightarrow \epsilon$

   Explanation

   Context-Sensitive Grammar (CSG, Type-1): Production $\alpha \rightarrow \beta$ where $\alpha,\beta \in (V\cup T)^*$ and $|\alpha| \le |\beta|$ (non-contracting), except possibly $S \rightarrow \epsilon$ with $S$ not appearing on RHS.

   Check each:

   • (i) $AB \rightarrow BA$ : $|\alpha|=2$, $|\beta|=2$ → $2 \le 2$ allowed (context-sensitive, length-preserving).
   • (ii) $A \rightarrow \epsilon$ : $|\alpha|=1$, $|\beta|=0$ → $1 \le 0$ false, contracting, not allowed in CSG (unless $A=S$ and $S$ is start with special $\epsilon$ rule).
   • (iii) $A \rightarrow a$ : $1 \le 1$ allowed.
   • (iv) $aB \rightarrow ab$ : $2 \le 2$ allowed (context $a$).

   Hence only $A \rightarrow \epsilon$ violates the monotonicity condition.

   Final Answer

   Not allowed: $A \rightarrow \epsilon$ → Option (ii).

6. Q1f. A Turing Machine that prints strings of a language is called (i) Acceptor (ii) Transducer (iii) Generator (iv) Enumerator20252m

   Module 4: Turing Machines (TM)

   A Turing Machine that prints strings of a language is called

   (i) Acceptor
   (ii) Transducer
   (iii) Generator
   (iv) Enumerator

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer

   Correct Option: (iii) Generator (also enumerated as Transducer/Enumerator in some texts — “Generator” is the term for printing strings)

   Explanation

   TM views:

   Mode	Description
   Acceptor / Recognizer	Decides $w\in L$ by accepting/rejecting (yes/no).
   Transducer	Computes function $f(w)$ on output tape.
   Generator / Enumerator	Prints (generates) strings of $L$ one after another on output tape (printer).
   Decider	Acceptor that always halts.

   A TM that prints strings of a language is called Generator (or Enumerator if it lists all). Many textbooks list (iii) Generator and (iv) Enumerator as synonyms; exam key typically Generator.

   Final Answer

   Generator (prints strings) → Option (iii). Enumerator is equivalent variant.

7. Q1g. If \Sigma = \{a, b\}, then \Sigma^* contains (i) Only finite strings (ii) Only infinite strings (iii) All finite strings over \Sigma including \epsilon (iv) Only strings of equal length20252m

   Module 1: Introduction & Regular Languages

   If $\Sigma = \{a, b\}$, then $\Sigma^*$ contains

   (i) Only finite strings
   (ii) Only infinite strings
   (iii) All finite strings over $\Sigma$ including $\epsilon$
   (iv) Only strings of equal length

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer

   Correct Option: (iii) All finite strings over $\Sigma$ including $\epsilon$

   Explanation

   Definition: $\Sigma^* = \bigcup_{i=0}^{\infty} \Sigma^i$, where $\Sigma^0 = \{\epsilon\}$, $\Sigma^1 = \Sigma$, $\Sigma^2 = \Sigma\Sigma$, ...

   For $\Sigma = \{a,b\}$:

   • $\epsilon$ (empty string, length 0) ∈ $\Sigma^*$
   • $a, b$ ∈ $\Sigma^*$
   • $aa, ab, ba, bb$ ∈ $\Sigma^*$
   • … all finite concatenations.

   Properties:

   • Countably infinite set.
   • Does not contain infinite strings (each string is finite; there are infinitely many strings, but each has finite length).
   • Not limited to equal length.

   Options:

   • (i) Only finite strings but missing $\epsilon$ → incomplete
   • (ii) Only infinite strings → false
   • (iv) Only equal length → false

   Final Answer

   All finite strings including $\epsilon$ → Option (iii).

8. Q1h. The \epsilon-closure of a state is (i) The set of states reachable using \epsilon only (ii) The set of unreachable states (iii) The set of final states (iv) The dead states20252m

   Module 1: Introduction & Regular Languages

   The $\epsilon$-closure of a state is

   (i) The set of states reachable using $\epsilon$ only
   (ii) The set of unreachable states
   (iii) The set of final states
   (iv) The dead states

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer

   Correct Option: (i) The set of states reachable using $\epsilon$ only

   Explanation

   $\epsilon$-closure $\text{ECLOSE}(q)$ for NFA-$\epsilon$:

   $\text{ECLOSE}(q) = \{ p \mid q \xrightarrow{\epsilon^*} p \}$ — all states reachable from $q$ by zero or more $\epsilon$-moves, including $q$ itself.

   Example: $q_0 \xrightarrow{\epsilon} q_1 \xrightarrow{\epsilon} q_2$ → ECLOSE($q_0$) = $\{q_0,q_1,q_2\}$.

   Used in subset construction for $\epsilon$-NFA → DFA/NFA conversion: $\delta_D(S,a) = \text{ECLOSE}(\bigcup_{q\in S} \delta(q,a))$.

   Other options are incorrect: not unreachable, not just finals, not dead states.

   Final Answer

   $\epsilon$-closure = states via $\epsilon$ only → Option (i).

9. Q1i. Which of the following CFLs is deterministic? (i) {a^n b^n} (ii) Arithmetic expressions (iii) Palindromes (iv) {ww^R}20252m

   Module 2: Context-Free Languages (CFL) and PDA

   Which of the following CFLs is deterministic?

   (i) {$a^n b^n$}
   (ii) Arithmetic expressions
   (iii) Palindromes
   (iv) {$ww^R$}

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer

   Correct Option: (i) $\{a^n b^n\}$

   Explanation

   Deterministic CFL (DCFL): Accepted by DPDA (deterministic pushdown).

   • (i) $\{a^n b^n\}$: DPDA can push $a$'s, then pop for $b$'s, deterministic (no choice). DCFL.
   • (ii) Arithmetic expressions (e.g., $E \rightarrow E+E \mid E*E$) → inherently ambiguous, CFL but not deterministic (needs guessing).
   • (iii) Palindromes $\{ww^R\}$ → not deterministic (needs to guess middle). $\{w\#w^R\}$ is DCFL, but plain palindromes is NPD A.
   • (iv) $\{ww^R\}$ similar to (iii) — not DCFL.

   Hence only $\{a^n b^n\}$ is deterministic.

   Final Answer

   $\{a^n b^n\}$ is DCFL → Option (i).

10. Q1j. Multi-tape TM is (i) More powerful than single-tape TM (ii) Less powerful (iii) Equivalent in power (iv) Not equivalent20252m

    Module 4: Turing Machines (TM)

    Multi-tape TM is

    (i) More powerful than single-tape TM
    (ii) Less powerful
    (iii) Equivalent in power
    (iv) Not equivalent

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Answer

    Correct Option: (iii) Equivalent in power

    Explanation

    Multi-tape TM vs Single-tape TM:

    • Power: Equivalent. Any $k$-tape TM can be simulated by single-tape TM with at most quadratic slowdown (or $O(t^2)$). Both accept exactly RE languages; deciders both accept Recursive languages.
    • Efficiency: Multi-tape can be faster (e.g., palindrome $O(n)$ vs $O(n^2)$ on single tape), but not more powerful in computability.
    • Construction: Single tape encodes $k$ tapes via tracks ($k$-track tape) + markers for heads.

    Therefore they are equally powerful (Turing-equivalent).

    Final Answer

    Equivalent in power → Option (iii).

11. Budget App•POCKETLY

    Pocketly on Android

    Log daily food, travel, and hostel expenses instantly. Set monthly spending limits and see where your money goes without complex spreadsheets.

    Install Pocketly
12. Q2a. Given the grammar G = (\{S\}, \{a, b\}, P, S) P: S \rightarrow aSb | ab Derive the string aabb using leftmost derivation, rightmost derivation and also draw the parse tree.20257m

    Module 2: Context-Free Languages (CFL) and PDA

    Given the grammar
    $G = (\{S\}, \{a, b\}, P, S)$
    $P: S \rightarrow aSb | ab$

    Derive the string aabb using leftmost derivation, rightmost derivation and also draw the parse tree.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Answer

    Grammar: $G = (\{S\}, \{a,b\}, P, S)$ with $P: S \rightarrow aSb \mid ab$

    1. Leftmost Derivation (LMD)

    At each step, replace the leftmost non-terminal.

    $$\begin{aligned} S &\Rightarrow_{\text{lm}} aSb & \text{(using $S \rightarrow aSb$)} \\ &\Rightarrow_{\text{lm}} aaSbb & \text{(using $S \rightarrow aSb$ on leftmost $S$)} \\ &\Rightarrow_{\text{lm}} aabbb & \text{(using $S \rightarrow ab$ on leftmost $S$)} \\ &= \mathbf{aabb} \end{aligned}$$

    LMD Steps: $S \xRightarrow{lm} aSb \xRightarrow{lm} aaSbb \xRightarrow{lm} aabbb = aabb$

    2. Rightmost Derivation (RMD)

    At each step, replace the rightmost non-terminal.

    $$\begin{aligned} S &\Rightarrow_{\text{rm}} aSb & \text{(using $S \rightarrow aSb$)} \\ &\Rightarrow_{\text{rm}} aaSbb & \text{(using $S \rightarrow aSb$ on rightmost $S$)} \\ &\Rightarrow_{\text{rm}} aabbb & \text{(using $S \rightarrow ab$ on rightmost $S$)} \\ &= \mathbf{aabb} \end{aligned}$$

    RMD Steps: $S \xRightarrow{rm} aSb \xRightarrow{rm} aaSbb \xRightarrow{rm} aabbb = aabb$

    Note: Since this grammar is unambiguous and has only one non-terminal, LMD and RMD coincide in the sequence of sentential forms.

    3. Parse Tree (Derivation Tree)

    Code

    Copy

                S
               /|\
              a S b
                |
                S
               /|\
              a S b
                |
                ab
    

    Text/Mermaid representation:

    MermaidDiagram

    Code

    Rendering diagram…

    Tree structure:

    • Root: $S$
    • Internal nodes: $S$ (non-terminals)
    • Leaves (yield): $a, a, b, b$ (reading left to right = aabb)
    • Height: 3 (excluding root)

    Verification

    • String generated: aabb ✓
    • Language of grammar: $L(G) = \{a^n b^n \mid n \ge 1\}$
    • aabb corresponds to $n=2$ ✓

    Final Answer

    LMD: $S \xRightarrow{lm} aSb \xRightarrow{lm} aaSbb \xRightarrow{lm} aabbb$
    RMD: $S \xRightarrow{rm} aSb \xRightarrow{rm} aaSbb \xRightarrow{rm} aabbb$
    Parse Tree: As shown above (yield = aabb).

13. Q2b. Explain the Chomsky hierarchy of languages with examples.20257m

    Module 1: Introduction & Regular Languages

    Explain the Chomsky hierarchy of languages with examples.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Answer

    Chomsky Hierarchy (Noam Chomsky, 1956) classifies formal grammars and their languages by production rule restrictions into 4 types, forming a strict containment hierarchy.

    ---

    Hierarchy Overview

    Type	Name	Production Form	Language Class	Recognizing Automaton
    Type-0	Unrestricted	$\alpha \rightarrow \beta$, $\alpha,\beta \in (V\cup T)^*$, $\alpha
    eq \epsilon$	Recursively Enumerable (RE)	Turing Machine (TM)
    Type-1	Context-Sensitive	$|\alpha| \le |\beta|$, $\alpha \rightarrow \beta$ with context	Context-Sensitive (CSL)	Linear Bounded Automaton (LBA)
    Type-2	Context-Free	$A \rightarrow \gamma$, $A \in V$, $\gamma \in (V\cup T)^*$	Context-Free (CFL)	Pushdown Automaton (PDA)
    Type-3	Regular	$A \rightarrow aB \mid a$ (right-linear) or $A \rightarrow Ba \mid a$ (left-linear)	Regular (REG)	Finite Automaton (DFA/NFA)

    Containment:
    $$\text{REG} \subset \text{DCFL} \subset \text{CFL} \subset \text{CSL} \subset \text{RE} \subset \text{ALL}$$
    Each is a proper subset of the next.

    ---

    Detailed Explanation with Examples

    Type-3: Regular Languages

    • Grammar: Right-linear ($A \rightarrow aB \mid a$) or Left-linear.
    • Automaton: DFA/NFA/$\epsilon$-NFA (equivalent power).
    • Properties: Closed under union, intersection, complement, concatenation, star. Membership in $O(n)$.
    • Example 1: $L = \{a^m b^n \mid m,n \ge 0\}$
      • Grammar: $S \rightarrow aS \mid bA \mid \epsilon$, $A \rightarrow bA \mid \epsilon$
    • Example 2: Binary strings with even number of 1's: $(0^*10^*1)^*0^*$
      • DFA: 2 states tracking parity

    Type-2: Context-Free Languages (CFL)

    • Grammar: $A \rightarrow \gamma$ (single non-terminal LHS).
    • Automaton: PDA (NPDA > DPDA in power).
    • Properties: Closed under union, concat, star. Not closed under intersection, complement. Parsing $O(n^3)$ (CYK).
    • Example 1: $L = \{a^n b^n \mid n \ge 0\}$ (matching counts)
      • Grammar: $S \rightarrow aSb \mid \epsilon$
      • PDA: push $a$'s, pop for $b$'s
    • Example 2: Balanced parentheses
      • Grammar: $S \rightarrow (S) \mid SS \mid \epsilon$
    • Example 3: $\{ww^R \mid w \in \{a,b\}^*\}$ (palindromes)
      • NPDA guesses middle

    Type-1: Context-Sensitive Languages (CSL)

    • Grammar: $|\alpha| \le |\beta|$, productions like $\alpha A \beta \rightarrow \alpha \gamma \beta$ (context around $A$).
    • Automaton: LBA = TM with tape bounded by $k|w|$.
    • Properties: Membership decidable (PSPACE-complete). Closed under union, intersection, complement.
    • Example: $L = \{a^n b^n c^n \mid n \ge 1\}$
      • Grammar: $S \rightarrow aBC \mid aSBC$, $CB \rightarrow BC$, $aB \rightarrow ab$, $bB \rightarrow bb$, $bC \rightarrow bc$, $cC \rightarrow cc$
      • Generates $a^n b^n c^n$ by expanding and reordering

    Type-0: Recursively Enumerable (RE)

    • Grammar: No restrictions (unrestricted).
    • Automaton: Turing Machine (TM).
    • Properties: Not closed under complement. Halting problem undecidable. Semi-decidable.
    • Example: $L = \{\langle M \rangle \mid M \text{ halts on empty input}\}$ (Halting problem)
    • Note: All computable languages are RE; recursive (decidable) are subset where TM always halts.

    ---

    Summary Table with Examples

    Type	Language	Grammar Example	Automaton
    3 (REG)	$(a+b)^*$	$S \rightarrow aS \mid bS \mid \epsilon$	DFA
    3 (REG)	$\{w \mid \#_0(w) \text{ even}\}$	$S \rightarrow 0S \mid 1A$, $A \rightarrow 0A \mid 1S$	DFA (2 states)
    2 (CFL)	$\{a^n b^n\}$	$S \rightarrow aSb \mid \epsilon$	PDA
    2 (CFL)	$\{ww^R\}$	$S \rightarrow aSa \mid bSb \mid \epsilon$	NPDA
    1 (CSL)	$\{a^n b^n c^n\}$	(as above)	LBA
    0 (RE)	Halting Problem	Unrestricted	TM

    ---

    Practical Implications

    • Type-3: Lexical analysis, regex matching
    • Type-2: Syntax analysis (parsers), programming language grammars
    • Type-1: Rare in practice; natural language features
    • Type-0: Theoretical limits, computability

    ---

    Final Answer

    Chomsky hierarchy organizes languages by grammar restrictiveness: Type-3 (Regular) ⊂ Type-2 (CFL) ⊂ Type-1 (CSL) ⊂ Type-0 (RE), each with corresponding automaton (FA, PDA, LBA, TM). Examples: REG → DFA, CFL → PDA, CSL → LBA, RE → TM.

14. Q3a. Design a context-free grammar (CFG) that generates all palindromes over the alphabet {0, 1}. The grammar should generate both even-length palindromes (e.g., 0110) and odd-length palindromes (e.g., 010).20257m

    Module 2: Context-Free Languages (CFL) and PDA

    Design a context-free grammar (CFG) that generates all palindromes over the alphabet {0, 1}. The grammar should generate both even-length palindromes (e.g., 0110) and odd-length palindromes (e.g., 010).

    View this question on its own page →

    CopySearch GoogleAsk AI
15. Q3b. Given the regular expression: (0+1)^*01(0+1) Describe the language generated, and construct an equivalent DFA.20257m

    Module 1: Introduction & Regular Languages

    Given the regular expression:
    $(0+1)^*01(0+1)$

    Describe the language generated, and construct an equivalent DFA.

    View this question on its own page →

    CopySearch GoogleAsk AI
16. Q4a. Given a DFA D over the alphabet {a, b}, perform DFA minimization and draw the equivalent minimal DFA accepting the same language. 20257m

    Module 1: Introduction & Regular Languages

    Given a DFA D over the alphabet {a, b}, perform DFA minimization and draw the equivalent minimal DFA accepting the same language.

    View this question on its own page →

    CopySearch GoogleAsk AI
17. Q4b. Use the pumping lemma to prove that the language L = \{a^n b^n : n \ge 1\} is not regular.20257m

    Module 1: Introduction & Regular Languages

    Use the pumping lemma to prove that the language $L = \{a^n b^n : n \ge 1\}$ is not regular.

    View this question on its own page →

    CopySearch GoogleAsk AI
18. Q5a. Show that the following grammar is ambiguous: S \rightarrow SS | aSb | bSa | \epsilon20257m

    Module 2: Context-Free Languages (CFL) and PDA

    Show that the following grammar is ambiguous:
    $S \rightarrow SS | aSb | bSa | \epsilon$

    View this question on its own page →

    CopySearch GoogleAsk AI
19. Q5b. Construct an NFA that accepts all strings over the alphabet {0, 1, 2} that begin with one or more 0s, followed by an odd number of 1s, and end with any number of 2s.20257m

    Module 1: Introduction & Regular Languages

    Construct an NFA that accepts all strings over the alphabet {0, 1, 2} that begin with one or more 0s, followed by an odd number of 1s, and end with any number of 2s.

    View this question on its own page →

    CopySearch GoogleAsk AI
20. Q6a. Prove that every context-free language is context-sensitive, but the converse is not true. Support your answer with a suitable language example.20257m

    Module 3: Context-Sensitive Languages

    Prove that every context-free language is context-sensitive, but the converse is not true. Support your answer with a suitable language example.

    View this question on its own page →

    CopySearch GoogleAsk AI
21. Q6b. Given the following context-sensitive grammar: S \rightarrow aSBC | abc CB \rightarrow BC aB \rightarrow ab bB \rightarrow bb bC \rightarrow bc cC \rightarrow cc Identify the language generated by the grammar. Derive the string aabbcc step by step.20257m

    Module 3: Context-Sensitive Languages

    Given the following context-sensitive grammar:
    $S \rightarrow aSBC | abc$
    $CB \rightarrow BC$
    $aB \rightarrow ab$
    $bB \rightarrow bb$
    $bC \rightarrow bc$
    $cC \rightarrow cc$

    Identify the language generated by the grammar. Derive the string aabbcc step by step.

    View this question on its own page →

    CopySearch GoogleAsk AI
22. Budget App•POCKETLY

    Pocketly on Android

    Log daily food, travel, and hostel expenses instantly. Set monthly spending limits and see where your money goes without complex spreadsheets.

    Install Pocketly
23. Q7a. Define a Linear Bounded Automaton (LBA). Design an LBA that accepts the language L = \{a^n b^n c^n | n \ge 1\}. Explain how tape length is restricted.20257m

    Module 3: Context-Sensitive Languages

    Define a Linear Bounded Automaton (LBA). Design an LBA that accepts the language $L = \{a^n b^n c^n | n \ge 1\}$. Explain how tape length is restricted.

    View this question on its own page →

    CopySearch GoogleAsk AI
24. Q7b. Design a Turing Machine that enumerates all strings over {a, b} in lexicographic order. Explain the working of the machine.20257m

    Module 4: Turing Machines (TM)

    Design a Turing Machine that enumerates all strings over {a, b} in lexicographic order. Explain the working of the machine.

    View this question on its own page →

    CopySearch GoogleAsk AI
25. Q8a. Design a single-tape Turing Machine that multiplies two unary numbers, where the input is of the form 1^m 0 1^n and the output is 1^{m \times n}. Clearly define the input alphabet, tape alphabet, and halting condition. Simulate the working of the Turing Machine on the input string 1101.20257m

    Module 4: Turing Machines (TM)

    Design a single-tape Turing Machine that multiplies two unary numbers, where the input is of the form $1^m 0 1^n$ and the output is $1^{m \times n}$. Clearly define the input alphabet, tape alphabet, and halting condition. Simulate the working of the Turing Machine on the input string $1101$.

    View this question on its own page →

    CopySearch GoogleAsk AI
26. Q8b. Given the regular expression r = (a+b)^* (i) Construct a context-free grammar that generates the language described by r. (ii) Explain why the grammar correctly represents the given regular expression.20257m

    Module 2: Context-Free Languages (CFL) and PDA

    Given the regular expression $r = (a+b)^*$

    (i) Construct a context-free grammar that generates the language described by $r$.
    (ii) Explain why the grammar correctly represents the given regular expression.

    View this question on its own page →

    CopySearch GoogleAsk AI
27. Q9a. Write a short note on Rice's Theorem with an application.20254.66m

    Module 5: Undecidability

    Write a short note on Rice's Theorem with an application.

    View this question on its own page →

    CopySearch GoogleAsk AI
28. Q9b. Write a short note on Deterministic vs Nondeterministic PDA.20254.66m

    Module 2: Context-Free Languages (CFL) and PDA

    Write a short note on Deterministic vs Nondeterministic PDA.

    View this question on its own page →

    CopySearch GoogleAsk AI
29. Q9c. Write a short note on Universal Turing Machine.20254.66m

    Module 5: Undecidability

    Write a short note on Universal Turing Machine.

    View this question on its own page →

    CopySearch GoogleAsk AI
30. Q9d. Write a short note on Greibach Normal Form (GNF).20254.66m

    Module 2: Context-Free Languages (CFL) and PDA

    Write a short note on Greibach Normal Form (GNF).

    View this question on its own page →

    CopySearch GoogleAsk AI