Register

GO Classes DPP | TOC|MEALY MACHINE

288 views
2 2 votes

A finite state machine is represented by the diagram below. It has two states, $Q_{\text {even }}$ (the start state) and $Q_{\text {odd }}$. The machine takes a binary string as input, processing it from left to right. For each input bit, it produces a single output bit.

The transitions are labeled with the format input/output.

Machine Description:

  • Start State: $Q_{\text {even }}$
     
  • Transitions from $Q_{\text {even }}$ :
     
  • A self-loop on input $\theta$ which outputs 1 . (Notation: $0 / 1$ )
     
  • A transition to state $Q_{\text {odd }}$ on input 1 which outputs 0 . (Notation: $1 / 0$ )
     
  • Transitions from $Q_{\text {odd }}$ :
     
  • A self-loop on input $\theta$ which outputs $\theta$. (Notation: $0 / 0$ )
     
  • A transition to state $Q_{\text {even }}$ on input 1 which outputs 1. (Notation: $1 / 1$ )

For an input string $w=w_1 w_2 \ldots w_n$, the machine produces an output string $z=z_1 z_2 \ldots z_n$.

Which of the following is TRUE about the output bit $z_i$ (the $i$-th bit of the output)?

  1. $z_i=1$ if and only if the number of $1$s in the input prefix $w_1 \ldots w_i$ is even.
     
  2. $z_i=1$ if and only if the number of $1$s in the input prefix $w_1 \ldots w_i$ is odd.
     
  3. $z_i=1$ if and only if the input bit $w_i$ is $0$.
     
  4. $z_i=1$ if and only if the number of $0$s in the input prefix $w_1 \ldots w_i$ is even.

1 Answer

1 1 vote

The state of the machine tracks the parity of the 1s seen so far:

  • $Q_{\text {even }}$ : The machine is in this state when it has processed an even number of 1 s.
     
  • $Q_{\text {odd }}$ : The machine is in this state when it has processed an odd number of 1 s.

Let's trace the input string 101 :

1. Start: The machine is in state $Q_{\text {even }}$.

2. Input $w_1=1$ :

  • The machine is in $Q_{\text {even }}$ and reads a 1.
     
  • According to the rules, it transitions to $Q_{\text {odd }}$ and outputs $z_1=0$.
     
  • At this point, the prefix processed is "1", which has an odd number of 1s.

3. Input $w_2=0$ :

  • The machine is in $Q_{\text {odd }}$ and reads a 0 .
     
  • It stays in $Q_{\text {odd }}$ and outputs $z_2=0$.
     
  • The prefix processed is " 10 ", which still has an odd number of 1 s.

4. Input $w_3=1$ :

  • The machine is in $Q_{\text {odd }}$ and reads a 1.
     
  • It transitions to $Q_{\text {even }}$ and outputs $z_3=1$.
     
  • The prefix processed is "101", which has an even number of 1s (two 1s).

Let's review the output based on this trace:

  • When the count of 1s in the prefix was odd ("1", " 10 "), the output was 0.
     
  • When the count of 1s in the prefix became even ("101"), the output was 1.

This behaviour directly corresponds to Option A:

A. $z_i=1$ if and only if the number of 1s in the input prefix $w_1 \ldots w_i$ is even.

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | TOC...Next → · GO Classes DPP | TOC...
← Previous in category · GO Classes DPP | TOC...Next in category → · GO Classes DPP | TOC...
Position:
Show:

Related questions

6 6 votes
2 2 answers
307
307 views
GO Classes asked Oct 8, 2025
307 views
GO Classes DPP | TOC | RE
If the regular set $\mathbf{A}$ is represented by $A=(b+a b)^*(a+\epsilon)$ and the regular set $\mathbf{B}$ is represented by $B=\left(b^* a b^*\right)^*(a+\epsilon)$, w...
5 5 votes
3 3 answers
379
379 views
GO Classes asked Oct 8, 2025
379 views
GO Classes DPP | TOC | RE
The string 'babaa' does not belong to the set represented by$\left(a^* b\right)^*(a+b)$ $b\left(a^* b^*\right)^* a$ $b\left(a+b^* a\right)^*$ $\left(b^* a\right)^*\left(a...
3 3 votes
3 3 answers
336
336 views
GO Classes asked Oct 8, 2025
336 views
GO Classes DPP | TOC | RE
Which two of the following four regular expressions are equivalent over the alphabet $\{a, b\}$ ? ( $\epsilon$ is the empty string).i. $(a+b)^*$ii. $a^*\left(b a^*\right)...
5 5 votes
4 4 answers
477
477 views
GO Classes asked Oct 8, 2025
477 views
GO Classes DPP | TOC|FA
Consider a Deterministic Finite Automaton (DFA) defined as follows:States $(Q):\left\{q_0, q_1, q_2, q_3, q_4\right\}$ Alphabet ( $\Sigma$ ): $\{a, b\}$ Start State: $q_0...