Algorithms and Programming: Problems and Solutions 1st. Edition by Alexander Shen | 9780817647605 | 0817647600 | Holooly

Information Technology

Algorithms and Programming: Problems and Solutions

239 SOLVED PROBLEMS

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. ...

Verified Answer:

Assume that an arbitrary input string is given. We...

Question: 10.2.3

as we said, the difficulty appears because there are several possible positions of the pattern; each position corresponds to some prefix of the pattern that is also a suffix of the input string. The finite automaton remembers only the longest one. What about others? ...

Verified Answer:

The longest prefix-suffix X determines all other p...

Question: 10.2.1

Can the previous algorithm be used for any other string instead of abcd? ...

Verified Answer:

A problem arises when the pattern contains repetit...

Question: 12.2.4

A leaf is added to or deleted from a balanced tree. Prove that it is possible to make the tree balanced again using several rotations and that the number of rotations does not exceed the tree height. ...

Verified Answer:

We prove the more general statement: Lemma. If a s...

Question: 14.4.7

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

Verified Answer:

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. ...

Verified Answer:

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. ...

Verified Answer:

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

Question: 14.4.4

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

Verified Answer:

(1) If a string S is coherent with a situation [K ...

Question: 14.4.3

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

Verified Answer:

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

Question: 14.4.2

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

Verified Answer:

Now a situation is defined as a pair [situation in...

Loading...