# Question 14.4.4: Show how to compute inductively the set State(S) of all ......

Show how to compute inductively the set State(S) of all situations coherent with a given string S.

Step-by-Step
The 'Blue Check Mark' means that this solution was answered by an expert.

(1) If a string S is coherent with a situation [K → U_V, t] and the first character in V is J, that is, V = JW, then SJ is coherent with the situation [K → UJ_W, t].

This rule determines completely which situations that do not start with underscore are coherent with SJ. It remains to find out for which nonterminals K and terminals t the string SJ belongs to Left(K, t). This is done according to the following two rules:

(2) If the situation [L → U_V, g] is coherent with SJ (according to (1)) and V starts with a nonterminal K, then SJ belongs to Left(K, s) for any terminal s that may appear as a first symbol in a string derivable from V \ K (the string V without the first symbol K), as well as for s = t, if the empty string is derivable from V \ K.

(3) If SJ is in Left(L, t) for some L and g, and L → V is a production rule, and V starts with a nonterminal K, then SJ belongs to Left(K, s) for any nonterminal s that may appear as a first symbol in a string derivable from V \ K, as well as for s = t, if the empty string is derivable from V \ K.

Question: 14.2.4

## Assume that an LR(0)-grammar is given. Prove that each string has at most one rightmost derivation. Give an algorithm that checks whether the input string is derivable. ...

Assume that an arbitrary input string is given. We...
Question: 14.4.7

## Find and prove the connection between the notions of LR(0)-coherence and LR(1)-coherence. ...

Assume that a grammar is fixed. The string S of te...
Question: 14.4.6

## For any LR(1)-grammar, construct an algorithm that checks if a given string is derivable in the grammar. ...

As before, at each stage of the LR-process we can ...
Question: 14.4.5

## Give the definition of the shift/reduce and shift/shift conflicts in the LR(1)-case. ...

Assume that a grammar is fixed. Let S be an arbitr...
Question: 14.4.3

## How to modify the definition of a string coherent with a situation? ...

The string S (of terminals and nonterminals) is co...
Question: 14.4.2

## How should we modify the definition of a situation? ...

Now a situation is defined as a pair [situation in...
Question: 14.3.3

## Check if the grammar shown above on p. 202 (having nonterminals E, T and F) is an SLR(1)-grammar. ...

Yes; both conflicts that prevent it from being a L...
Question: 14.4.1

## Write a grammar whose nonterminals generate the sets Left(K, t) for all nonterminals K of the given grammar. ...

Nonterminals are symbols (LeftK t) for any nonterm...
Question: 14.2.3