Register

TIFR CSE 2010 | Part B | Question: 22

• edited by
2,033 views
21 votes
21 votes

Let $L$ consist of all binary strings beginning with a $1$ such that its value when converted to decimal is divisible by $5$. Which of the following is true?

  1. $L$ can be recognized by a deterministic finite state automaton.
  2. $L$ can be recognized by a non-deterministic finite state automaton but not by a deterministic finite state automaton.
  3. $L$ can be recognized by a deterministic push-down automaton but not by a non-deterministic finite state automaton.
  4. $L$ can be recognized by a non-deterministic push-down automaton but not by a deterministic push-down automaton.
  5. $L$ cannot be recognized by any push-down automaton.
• edited by
User Avatar

2 Answers

Best answer
19 votes
19 votes

$L$ can be recognized by a dfa. we have a dfa to accept all such strings which when interpretated as decimal number are divisible by $n$. Where $n$ can be anything the dfa of such can be made by a trick.

 States are equal to possible remainders

$$\overset{\text{Transition Table}}{\begin{array}{|c|c|c|c|}\hline
\textbf {} & \textbf {0} & \textbf{1} \\\hline
q_0   & q_0 & q_1  \\ \hline   
q_1 & q_2 & q_3   \\\hline
q_2  & q_4 & q_0   \\\hline q_3  & q_1 & q_2   \\\hline q_4  &q_3 & q_4   \\\hline
\end{array}}$$

If you can see the symmetry in it. write states and make fill like $q_0 \ q_1 \ q_2 \ q_3\ q_4\ q_0 ...$

Now, it is saying that it has to always start with $1$ which the above dfa will not satisfy so make it a nfa by making  a transition from $q_0$ on zero to a new dead state. now you have a nfa reduce it which will result in a deterministic DFA .

So, option is A.

• edited by
User Avatar
13 votes
13 votes
Binary strings beginning with a. (Regular)
Binary strings divisible by 5 (Regular)
Regular languge are closed under intersection. Hence the given language is regular.
Now comes DFA or NFA. You know both are equivalent.
Hence i) is the answer.
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

21 votes
21 votes
3 answers
3
makhdoom ghaya asked Oct 10, 2015
2,630 views
TIFR CSE 2010 | Part B | Question: 34
Let $r, s, t$ be regular expressions. Which of the following identities is correct? $(r + s)^* = r^*s^*$ $r(s + t) = rs + t$ $(r + s)^* = r^* + s^*$ $(rs + r)^* r = r (sr + r)^*$ $(r^*s)^* = (rs)^*$
Let $r, s, t$ be regular expressions. Which of the following identities is correct?$(r + s)^* = r^*s^*$$r(s + t) = rs + t$$(r + s)^* = r^* + s^*$$(rs + r)^* r = r (sr + r...
User Avatar
Link Copied!