How to convert recursive language grammar tree into automaton for optimal parsing?

So I have a definition of a sort of grammar for a programming language. Some aspects are recursive (like nesting function definitions), other parts of it are just simple non-recursive trees.

Originally I just treat this sort of like a Parsing Expression Grammar (PEG), and parse it using recursive descent. But this is kind of inefficient, as it sometimes has to build up objects as it’s parsing, only to find 10 calls down the road that it isn’t a good match. So then it backs up and has to try the next pattern.

I’m wondering what the general solution to this is. What can be done to create the most optimal algorithm starting from nothing but a tree-like data structure encoding the grammar?

Can you process the tree-like, recursive-ish BNF PEG data structure in a while loop, rather than using recursive descent? Better still, can you convert the data structure into a sort of automaton which you can (in some simple way) transition through, to parse the string without having to go down a bunch of wrong paths and generate stuff you only have to soon throw away if you find it’s a mismatch? Or if not, is there anything that can be done here with automata?

Sorry for my terminology (BNF vs. PEG), I am not using it exactly. I just mean I have a grammar, which is context-sensitive which falls outside the scope of either of these. So I am picking one or the other to simplify this question for the purpose of this site, even though I’m not 100% sure what the difference between BNF and PEG are at this point.

Is my recursive algorithm for Equivalent Words correct?

Here is my problem.

Problem Given two words and a dictionary, find out whether the words are equivalent.

Input: The dictionary, D (a set of words), and two words v and w from the dictionary.

Output: A transformation of v into w by substitutions such that all intermediate words belong to D. If no transformation is possible, output “v and w are not equivalent.”

I need to write both recursive and dynamic programming algorithm. As for recursion, I came up with this algorithm. Is it correct?

 EquivalentWordsProblem(v, w, D)  1.m <- len (v)  2.n <-  len (w)  3.substitutions = [] #array to save substitutions   4.if m != n:  5.  return "v and w are not equivalent"  6.else  7.for i <- m to 1 <-1 do  8.  for j <- n to j <- 1 do  9.    if v[i] != w[j]:  10.           substituted_word <- v[1…i-1]+v[j] #we substitute v[i] for w[j]  11.              if substituted_word in D:  12.                substitutions.append(substituted_word)  13.                   return EquivalentWordsProblem(v[1…m-i], w, D) #recur on the string of length m - i  14.   else:          return EquivalentWordsProblem(v[1…m-1], w, D) #recur on the string decreasing its length by 1  15.if len(substitutions) != 0:  16.  return substitutions   17.else  18.   return (“v and w are not equivalent”)  

Recurrence relation for the number of “references” to two mutually recursive function

I was going through the Dynamic Programming section of Introduction to Algorithms(2nd Edition) by Cormen et. al. where I came across the following recurrence relations in the assembly line scheduling portion.


$ (1),(2),(3)$ are three relations as shown.

$ $ f_{1}[j] = \begin{cases} e_1+a_{1,1} &\quad\text{if } j=1\ \min(f_1[j-1]+a_{1,j},f_2[j-1]+t_{2,j-1}+a_{1,j})&\quad\text{if} j\geq2\ \end{cases}\tag 1$ $

Symmetrically,

$ $ f_{2}[j] = \begin{cases} e_2+a_{2,1} &\quad\text{if } j=1\ \min(f_2[j-1]+a_{2,j},f_1[j-1]+t_{1,j-1}+a_{2,j})&\quad\text{if} j\geq2\ \end{cases}\tag 2$ $

(where $ e_i,a_{i,j},t_{2,j-1}$ are constants for $ i=1,2$ and $ j=1,2,3,…,n$ )

$ $ f^\star=\min(f_1[n]+x_1,f_2[n]+x_2)\tag 3$ $


The text tries to find the recurrence relation of the number of times $ f_i[j]$ ($ i=1,2$ and $ j=1,2,3,…,n$ ) is referenced if we write a mutual recursive code for $ f_1[j]$ and $ f_2[j]$ . Let $ r_i(j)$ denote the number of times $ f_i[j]$ is referenced.

They say that,

From $ (3)$ ,

$ $ r_1(n)=r_2(n)=1.\tag4$ $

From $ (1)$ and $ (2)$ ,

$ $ r_1(j)=r_2(j)=r_1(j+1)+r_2(j+1)\tag 5$ $


I could not quite understand how the relations of $ (4)$ and $ (5)$ are obtained from the three corresponding relations.

Thought I could make out intuitively that as there is only one place where $ f_1[n]$ and $ f_2[n]$ are called, which is in $ f^\star$ , so probably in $ (4)$ we get the required relation.

But as I had not encountered such concept before I do not quite know how to proceed. I would be grateful if someone guides me with the mathematical prove of the derivation as well as the intuition, however I would prefer an alternative to mathematical induction as it is a mechanical cookbook method without giving much insight into the problem though (but if in case there is no other way out, then I shall appreciate mathematical induction as well provided the intuition is explained to me properly).

Simplifying Function with Recursive CTE and/or Window Function

I’m trying to come up with a Recursive CTE and/or Window Function to create a function.

After days, I’ve boiled the function down to (pseudocode) where I have N and B, and need to generate E:

En = Bn * (1 – SUM(E1, E2, … En-1))

Examples:

╔═══╦═════════════╦═════════════╗ ║ N ║ B           ║ E           ║ ╠═══╬═════════════╬═════════════╣ ║ 0 ║ 0.142857143 ║ 0.142857143 ║ ║ 1 ║ 0.285714286 ║ 0.244897959 ║ ║ 2 ║ 0.285714286 ║ 0.174927114 ║ ║ 3 ║ 0.285714286 ║ 0.124947938 ║ ║ 4 ║ 0.285714286 ║ 0.089248527 ║ ║ 5 ║ 0.4         ║ 0.089248527 ║ ║ 6 ║ 0.666666667 ║ 0.089248527 ║ ║ 7 ║ 1           ║ 0.044624264 ║ ╚═══╩═════════════╩═════════════╝ 

E0 = 0.143 * (1 – 0) = 0.143
E1 = 0.286 * (1 – 0.143) = 0.245
E2 = 0.286 * (1 – (0.143 + 0.245)) = 0.175
E3 = 0.286 * (1 – (0.143 + 0.245 + 0.175)) = 0.125
E4 = 0.286 * (1 – (0.143 + 0.245 + 0.175 + 0.125)) = 0.089
E5 = 0.400 * (1 – (0.143 + 0.245 + 0.175 + 0.125 + 0.089)) = 0.089
E6 = 0.667 * (1 – (0.143 + 0.245 + 0.175 + 0.125 + 0.089 + 0.089)) = 0.089
E7 = 1.000 * (1 – (0.143 + 0.245 + 0.175 + 0.125 + 0.089 + 0.089 + 0.089)) = 0.044

If the table above was in Excel, C2 = B2 * (1 - 0) (base) and C3 = B3 * (1 - SUM(C$ 2:C2)) (recursive)

What I’ve tried:

Windowed Functions

Tried SUM(...) OVER(ORDER BY [N] ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING), but can’t reference the column recursively.

Recursive CTE

Tried several iterations of:

WITH B AS ([Num], [Best], [Effective Rate]) AS (     SELECT *         , [Best]     FROM A     WHERE [Num] = 0     UNION ALL     SELECT A.*         , (1 - [Effective Rate]) * A.[Best]     FROM B     JOIN A ON A.[Num] = B.[Num] + 1  ) 

and some with an extra column in the CTE, but it only covers 1 previous row and results after 2nd row are wrong.

Recursive CTE with Windowed Function

From all that I’ve tried, it seems that the recursive segment of the CTE is calculated independently of the other results, and SUM(...) OVER(...) only works on the current row. (With regard to the above table, all values of E would be 0.142857143).

I assume this is because the UNION ALL happens all at once, and not incrementally.

Alternative Solutions

What I would really like to happen is to simplify the above equation, and/or transform it into an iterative function.

Bonus: If anyone cares to know the source of this information, it’s used to calculate MACRS depreciation for tax purposes.

Proving a certain primitive recursive function exists

Assume $ f\colon ω × ω → ω$ is a computable function. How can we prove that there is a primitive recursive function $ g\colon ω × ω → ω$ where the following holds:

$ ∀n [∃s(f(n, s) = 1) ↔ ∃k(g(n, k) = 1)]$

So for every $ n$ , there is an $ s$ such that $ f(n, s) = 1$ if and only if there is a $ k$ such that $ g(n, k) = 1$ .

Been working on this problem for a while now, if anyone could please help?

Calculating complexity for recursive algorithm with codependent relations

I wrote a program recently which was based on a recursive algorithm, solving for the number of ways to tile a 3xn board with 2×1 dominoes:

F(n) = F(n-2) + 2*G(n-1)

G(n) = G(n-2) + F(n-1)

F(0) = 1, F(1) = 0, G(0) = 0, G(1) = 1

I tried to calculate the complexity using methods I know such as recursion tree and expansion, but none resulted in any answer. Actually I had never come across such a recursion, where the relations are codependent.

Am I using the wrong methods, or maybe using the methods in a wrong way? And if so, can anyone offer a solution?

Time Complexity of Recursive Ray Tracing with respect to Depth

How does depth of ray tracing affect the run time (role in the complexity) of the recursive ray tracing algorithm with reflection and refraction?

How I have calculated it is, for each ray after intersection, it is split to 2 rays (one for reflection and one is the refracted ray), so the complexity with respect to depth would be exponential time ~O(2^D) for the ray tracing depth D. And for the image resolution of M*N, the complexity would be O(M.N.2^D).

Would you confirm these results, or am I missing something?