How to turn a context-free grammar into a stack automaton?

Asked

Viewed 1,775 times

3

I have a grammar, like for example:

gramática que obriga a quantidade de b's ser entre [1,2] vezes a quantidade de a's

Or else:

gramática regular, portanto também livre de contexto

Or even that:

outra gramática regular da qual eu me lembrei

Or this grammar, which represents the boolean logic for three variables:

gramática para operações booleanas

  • How to turn these grammars into stack automata?
  • Would have some relationship between states and nonterminals?
  • Could show the execution of this algorithm for the given grammars as an example?

Related:

algorithm computer-theory automata formal-languages

1 answer

2


There is an algorithm that allows you to do just that, turn any grammar into a nondeterministic stack automaton. The idea is that all grammatical production consumes at most an element of the input word. For this, all production must contain terminal only at the beginning, if it contains some terminal, and only in the amount of one.

For example, some of the productions that satisfy this condition are:

  • S -> b B1
  • O -> A B_op A
  • S -> lambda

Examples of unsatisfactory productions:

  • S -> aSb
  • S -> aSbb
  • A -> ( O )

because it contains terminals on the right.

For these cases, we create a new nonterminal equivalent to the terminal in question. For example:

  • S -> aSb, using B for the non-terminal equivalent of b:
    • S -> aSB
  • S -> aSbb, using B for the non-terminal equivalent of b:
    • S -> aSBB
  • A -> ( O ), using F for the non-terminal equivalent of ):
    • A -> ( O F

After running this process, the following new grammars were produced:

Note: they are equivalent to the previous ones; I only show here the grammars that had new productions created according to the algorithm described above.

quantidades de b's entre 1 e 2 vezes a de a, contanto que todos os a's estejam aglutinados à esquerda

And also:

mais outra gramática livre de contexto

And also

gramática normalizada para operações lógicas

Creating the stack automaton

The first step to creating the stack automaton is to place the initial nonterminal at the beginning of the stack. This is done by applying the following skeleton:

esqueleto autômato de pilha

Note that here the transition contains 3 elements, one before the comma and two after the comma, separated by a bar.

In this case, the value before the comma indicates what is being consumed from the input word. How is - skeleton, this means that at this time no input word character is being used.

The next two elements after the comma are -/S. In this case, this means that by not consulting the battery head (indicated by -), the non-terminal will be inserted S in the pile. Note that on the left side of the bar there can be only one element, corresponding to the top of the stack, but there can be several elements on the right side.

The next entered transactions all originate from the state ap and flow into the state ap of the above described automaton skeleton. Note that in this case there are transitions of the type -,-/- back and forth from another state x whichever, ap and x are equivalent. The transaction -,-/- does not consume anything of the input word, does not query or change the stack.

Note that it is only possible to fall into this stack automaton transformation algorithm after transforming the non-initial terminals of the production rules into non-equivalent terminals.

The word is only accepted, in this case, when all the characters of the input word have been consumed and with empty stack.

Productions that consume cell and input word elements

Let’s look at the case of S -> b B1. To transform into an automaton transition, the letter must be consumed b of the entrance, S from the top of the stack and should be inserted B1 on the pile. Therefore, production should be b,S/B1.

Productions that consume stack elements but not input word

Let’s study two cases for this one:

  • S -> lambda
  • O -> A B_op A

For the case S -> lambda, the transformation simply consumes S from the top of the stack. Therefore, it is -,S/-.

To O -> A B_op A, we consume O and put in the pile A B_Op A. Therefore, the transaction is -,O/A B_op A.

First grammar transformed into stack automaton

The first grammar has already undergone normalization. The normalization algorithm has been applied and obtained:

quantidades de b's entre 1 e 2 vezes a de a, contanto que todos os a's estejam aglutinados à esquerda

With this, we have the following transitions from ap for ap:

  • a,S/S B
  • a,S/S B B
  • b,B/-
  • -,S/-

For the sake of readability, I created a state a1 equivalent to ap:

autômato de pilha

Second grammar transformed into stack automaton

The second grammar has been normalized to this form here:

mais outra gramática livre de contexto

Therefore, your transitions are:

  • -,S/Nb S
  • b,S/B1
  • b,B1/B2
  • b,B2/B2
  • a,B2/A
  • -,B1/Nb S
  • -,B2/Nab S
  • -,A/Nb S
  • a,Nb/-
  • c,Nb/-
  • d,Nb/-
  • c,Nab/-
  • d,Nab/-

Later I’ll put the automaton here

Third stack automaton grammar

This grammar did not need any transformation, it was already normalized enough.

Later I’ll put the transactions and the automaton here

Fourth grammar transformed into stack automaton

This grammar needed to normalize only the question of closed parentheses, thus:

gramática normalizada para operações lógicas

Your transactions are (considering initial status O):

  • -,O/A
  • (,A/O F
  • ),F/-
  • -,O/A Bo A
  • -,O/Uo A
  • a,A/-
  • b,A/-
  • c,A/-
  • ¬,Uo/-
  • ^,Bo/-
  • v,Bo/-
  • =>,Bo/-
  • <=>,Bo/-

The following stack automaton recognizes this language:

autômato de pilha que reconhece expressões em álgebra booleana de até 3 variáveis

Browser other questions tagged algorithm computer-theory automata formal-languages

You are not signed in. Login or sign up in order to post.