Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

# TOC-grand test-Q9

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177
+1 vote

Consider the following problems concerning finite automata with alphabet $\small \{0,1\}$. Which of the following are DECIDABLE ?

S1 : on input a DFA D, determine whether D accepts infinitely many palindromes.

S2 : on input a DFA D; determine whether D accepts a pair of distinct strings u and v such that u is a prefix of v.

(A) Only S1

(B) Only S2

(C) Both S1 and S2

(D) Neither S1 or S2

reshown Sep 8, 2019

S1 : DECIDABLE,

Rephrasing, we need to determine whether $L(D) \cap P$ is infinite, where P is the context-free language of palindromes. Construct a PDA for $L(D) \cap P$ by applying the Cartesian-product construction to a PDA for P and the given DFA D. Then, convert the resulting PDA to a grammar and use the algorithm from class to check whether the grammar accepts infinitely many strings.

S2 : DECIDABLE ,

Use any graph search algorithm to identify the set $F'$ of accept states of D that are reachable from the start state. Output “yes” if and only if there exists a pair of state $q' , q'' \in F$ (not necessarily distinct) with a path of nonzero length from $q' to q''$)

Hence Option C

answered Sep 11, 2019 by (91,540 points)