TeX에서 LR (0) DFA와 같은 강한 오토 마톤을 그립니다.

리포트 등으로 오토마톤을 그리고 싶어지는 경우가 있다고 생각합니다. 「TeX 오토마톤」으로 구그하면, TikZ의 automata 라이브러리로 오토마톤을 그리는 방법이 여러가지 기사로 해설되고 있습니다.
그 예에서 등장하는 오토마톤은 아무도 원형으로 화살표가 자라는 단순한 그림입니다. 그렇다면 다음과 같은 상태 천이도는 automata 라이브러리로 그릴 수 있습니까?



이것은 ANDREW W. APPEL, Modern Compiler Implementation in ML이라는 책에 나오는 LR(0) DFA라는 오토마톤입니다. 이 오토마톤은
\begin{align}
S &\rightarrow E \$ \\
E &\rightarrow T \\ 
E &\rightarrow T + E \\
T &\rightarrow x
\end{align}

라고 하는 언어에 대응하고 있어, LR(0) 의 경우 shift 와 reduce 가 충돌해 해석할 수 없습니다만, SLR (Simple LR(1)) 의 경우 해석할 수 있습니다.

자, 이것을 그려 보겠습니다.
\usepackage{tikz}

\usetikzlibrary{automata}

\begin{tikzpicture}
  [>=latex, 
    node distance=3cm, 
    block/.style={state, rectangle, text width=6em}
  ]

  \node [block, label=above right:1] (q_0) 
    {
      \( S \rightarrow . E \$ \) \\
      \( E \rightarrow . T + E \) \\
      \( E \rightarrow . T \) \\
      \( T \rightarrow . x \) 
    };
  \node [block, label=above right:2] (q_1) [right of = q_0]
    {
      \( S \rightarrow E . \$ \)
    };
  \node [block, label=above right:3] (q_2) [below of = q_1] 
    {
      \( E \rightarrow T . + E \) \\
      \( E \rightarrow T . \)
    };
  \node [block, label=above right:4] (q_3) [below of = q_2]
    {
      \( E \rightarrow T + . E \) \\
      \( E \rightarrow . T + E \) \\
      \( E \rightarrow . T \) \\
      \( T \rightarrow . x \) 
    };
  \node [block, label=above right:5] (q_4) [left of = q_3]
    {
      \( T \rightarrow x . \)
    };
  \node [block, label=above right:6] (q_5) [right of = q_3]
    {
      \( E \rightarrow T + E . \)
    };

  \path [->] (q_0) edge [right]      node [above] {\(E\)} (q_1)
                   edge [right]      node [above] {\(T\)} (q_2)
                   edge [right]      node [left]  {\(x\)} (q_4)
             (q_2) edge [bend right] node [left]  {\(+\)} (q_3)
             (q_3) edge [right]      node [above] {\(x\)} (q_4)
                   edge [bend right] node [right] {\(T\)} (q_2)
                   edge [right]      node [above] {\(E\)} (q_5);
\end{tikzpicture}

그러면



그 문장을 그릴 수있었습니다.

일부 포인트
  • node 의 style 로 rectangle 를 지정하는 것으로, 상태의 부분을 사각형으로 할 수가 있습니다.
  • node 의 style 로 text width 를 지정하는 것으로, 안에서 개행을 할 수 있게 됩니다.
  • 중에서 복수행의 수식을 쓸 때, 보통으로 align (만약 오토마톤 이외에서 수식을 사용하지 않는다면, 글로벌 옵션으로 여백의 크기를 바꾸어 버려도 좋다고 생각합니다만).
  • 좋은 웹페이지 즐겨찾기