Contents    Page-10    Prev    Next    Page+10    Index   

Example Regular Language

A binary integer can be specified by a regular grammar:

<S> → 0 <S>
<S> → 1 <S>
<S> → 0
<S> → 1

The following is a parse tree for the string 110101. Note that the tree is linear in form; this is the case for any regular language. 


    S              110101
   / \ 
  1   S
     / \ 
    1   S
       / \ 
      0   S
         / \ 
        1   S
           / \ 
          0   S
             /
            1