Internet programming

• Decidability in Formal Languages and Automata:
• Decidable Problems:
• Equivalence of two finite automata: Decidable by testing language emptiness of $(L_1 \cap \overline{L_2}) \cup (\overline{L_1} \cap L_2)$.
• Membership for CFG: Decidable via CYK or Earley parsing algorithm ($O(n^3)$).
• Finiteness for FA: Decidable by checking cycles on paths to accepting states.
• Undecidable Problem:
• Ambiguity of Context-Free Grammars: Whether an arbitrary CFG is ambiguous (can generate two distinct parse trees for the same string) is proven to be Undecidable by reduction from Post's Correspondence Problem (PCP).
• Conclusion: Ambiguity problem for context free grammar (Option 4).

Correct option: (4) Ambiguity problem for context free grammar

• Regular Expression from DFA Transition Analysis:
• From start state $s$:
• single transition on input 1 reaches the accepting state $p$.
• At accepting state $p$:
• Reading 0 loops back to $p$.
• Reading 11 transitions through state $q$ and loops back to $p$.
• Any repetition of 0 and 11 keeps the machine in accepting state $p$.
• The complete regular expression for strings driving the DFA from $s$ to $p$ is:

• Conclusion: 1(0 + 11)* (Option 3).

Correct option: (3) 1(0+ 11)"