Book examples¶

This notebook provides examples of very simple grammars taken from two well-known textbooks on formal language theory.

[1]:

import alogos as al

1) Sipser¶

Reference: Sipser: Introduction to the theory of computation, 3rd edition, 2013

a) Palindromes¶

Grammar on p. 102
Derivation on p. 102
Parse tree on p. 103

[2]:

bnf_text = """
<A> ::= 0<A>1
<A> ::= <B>
<B> ::= #
"""

grammar = al.Grammar(bnf_text=bnf_text)

[3]:

grammar.generate_language(max_steps=10)

[3]:

['#',
 '0#1',
 '00#11',
 '000#111',
 '0000#1111',
 '00000#11111',
 '000000#111111',
 '0000000#1111111',
 '00000000#11111111']

[4]:

parse_tree = grammar.parse_string('000#111')
parse_tree

[4]:

[5]:

derivation = parse_tree.derivation()
print(derivation)

<A>
=> 0<A>1
=> 00<A>11
=> 000<A>111
=> 000<B>111
=> 000#111

b) Expressions¶

Grammar on p. 105
Parse tree on p. 105

[6]:

bnf_text = """
<expr> ::= <expr>+<term> | <term>
<term> ::= <term>*<factor> | <factor>
<factor> ::= (<expr>) | a
"""

grammar = al.Grammar(bnf_text=bnf_text)

[7]:

grammar.generate_language(max_steps=5, sort_order='shortlex')

[7]:

['a',
 'a*a',
 'a+a',
 'a*a*a',
 'a*a+a',
 'a+a*a',
 'a+a+a',
 'a*a+a*a',
 'a+a*a*a',
 'a+a*a+a',
 'a+a+a*a',
 'a*a+a*a*a',
 'a+a*a+a*a',
 'a+a+a*a*a',
 'a+a*a+a*a*a']

[8]:

parse_tree = grammar.parse_string('a+a*a')
parse_tree

[8]:

[9]:

parse_tree = grammar.parse_string('(a+a)*a')
parse_tree

[9]:

2) Hopcroft and Ullman¶

Reference: Hopcroft, Ullman: Introduction to Automata Theory, Languages, and Computation, 3rd edition, 2007

a) Palindromes¶

Grammar on p. 173
Parse tree on p. 185

[10]:

bnf_text = """
<P> ::=
      | 0
      | 1
      | 0<P>0
      | 1<P>1
"""

grammar = al.Grammar(bnf_text=bnf_text)

[11]:

grammar.generate_language(max_steps=3, sort_order='shortlex')

[11]:

['',
 '0',
 '1',
 '00',
 '11',
 '000',
 '010',
 '101',
 '111',
 '0000',
 '0110',
 '1001',
 '1111',
 '00000',
 '00100',
 '01010',
 '01110',
 '10001',
 '10101',
 '11011',
 '11111']

[12]:

parse_tree = grammar.parse_string('0110')
parse_tree

[12]:

b) Expressions¶

Grammar on p. 174
Derivation on p. 178 (leftmost) and p. 179 (rightmost)
Parse tree on p. 186

[13]:

bnf_text = """
<E> ::= <I>
      | <E>+<E>
      | <E>*<E>
      | (<E>)
<I> ::= a
      | b
      | <I>a
      | <I>b
      | <I>0
      | <I>1
"""

grammar = al.Grammar(bnf_text=bnf_text)

[14]:

language = grammar.generate_language(max_steps=3, sort_order='shortlex')
language

[14]:

['a',
 'b',
 'a0',
 'a1',
 'aa',
 'ab',
 'b0',
 'b1',
 'ba',
 'bb',
 '(a)',
 '(b)',
 'a*a',
 'a*b',
 'a+a',
 'a+b',
 'b*a',
 'b*b',
 'b+a',
 'b+b']

[15]:

parse_tree = grammar.parse_string('a*(a+b00)')
parse_tree

[15]:

[16]:

lm_derivation = parse_tree.derivation('leftmost')
print(lm_derivation)

<E>
=> <E>*<E>
=> <I>*<E>
=> a*<E>
=> a*(<E>)
=> a*(<E>+<E>)
=> a*(<I>+<E>)
=> a*(a+<E>)
=> a*(a+<I>)
=> a*(a+<I>0)
=> a*(a+<I>00)
=> a*(a+b00)

[17]:

rm_derivation = parse_tree.derivation('rightmost')
print(rm_derivation)

<E>
=> <E>*<E>
=> <E>*(<E>)
=> <E>*(<E>+<E>)
=> <E>*(<E>+<I>)
=> <E>*(<E>+<I>0)
=> <E>*(<E>+<I>00)
=> <E>*(<E>+b00)
=> <E>*(<I>+b00)
=> <E>*(a+b00)
=> <I>*(a+b00)
=> a*(a+b00)