0
$\begingroup$

I'm taking an automata class and one of the examples is showing this is regular. My initial thought was to make a DFA to show it is but i'm a bit confused on what a DFA with a standard 5 tuple would look like for this. I know my alphabet is all the combinations of 0,1,2 for the columns and that my final state would be when ternary number on the top would be larger. But i'm confused on my set of states, transition function, and how to write this all in a 5 tuple form. Any hints?

Let Σ3 be the alphabet that contains all columns of 0,1,2 of height two:

Σ2={[00],[01],[10],[11],[02],[20],[12],[21],[22]}. A string of symbols in Σ3 gives two rows of digits, we see each row as a ternary number. For instance [20][11][01] has a top row of 210 in ternary, which is 21 in decimal, and a bottom row of 011 in ternary, which is 4 in decimal.

Show that the following language is regular:

D={w∈Σ∗3∣the top row of w is a larger number than is the bottom row}. For instance, [00][20][02][00]∈D but [00][01][11][00]∉D .

Hint: Each element of Σ3 you read corresponds to the same position in the top and bottom numbers.

$\endgroup$

1 Answer 1

1
$\begingroup$

Note that for two ternary numbers $x = x_1x_2...x_n$ and $y = y_1y_2...y_n$ with digits $x_i$ and $y_i$ holds that $$x < y \iff x_1x_2...x_n \prec y_1y_2...y_n$$ where $\prec$ is supposed to be the lexicographic order (dictionary order) of strings. In general

  • $x_1x_2...x_n \prec y_1y_2...y_n$ if $x_1 < y_1$ or
  • $x_1x_2...x_n \prec y_1y_2...y_n$ if $x_1 = y_1$ and $x_2...x_n \prec y_2...y_n$.

So the language can be decided by reading pairs of digits $\begin{bmatrix} x_i \\ y_i \end{bmatrix}$ from left to right, and either going into an accepting state if $x_i > y_i$, going into a dead state if $x_i < y_i$ or simply continuing to read if $x_i = y_i$.

The corresponding DFA recognising $D$ can be defined as follows:

Define the DFA $A = (Q = \{q_=, q_>, q_<\}, \Sigma_3, \delta, q_=, F = \{q_>\})$ such that $$\delta(q_=, \begin{bmatrix} x \\ y \end{bmatrix}) = \begin{cases} q_> & \text{if } x > y \\ q_= & \text{if } x = y \\ q_< & \text{if } x < y \end{cases}$$ and $\delta(q_>, \begin{bmatrix} x \\ y \end{bmatrix}) = q_>$ as well as $\delta(q_<, \begin{bmatrix} x \\ y \end{bmatrix}) = q_<$ for all $\begin{bmatrix} x \\ y \end{bmatrix} \in \Sigma_3$.

A proof that $L(A) = D$ is best left to the reader ;)

$\endgroup$
2
  • $\begingroup$ Thank you so much, seeing it explained like that really helps me put things in their proper format, also helps with understanding the whole problem more! $\endgroup$
    – user167205
    Feb 12 at 21:53
  • $\begingroup$ @user167205 Nice, I'm happy to hear that :] $\endgroup$
    – Knogger
    Feb 12 at 22:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.