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

Question

I have a grammar, like for example:

Or else:

Or even that:

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

• 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:

• What is a context-free language?
• Could someone help me with this formal language?
• What is a language meta?
• Regular expression to recognize language: words that do not contain "bbab"

Answer 1

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.

And also:

And also

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:

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:

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:

Second grammar transformed into stack automaton

The second grammar has been normalized to this form here:

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:

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: