Questions tagged [derivation]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
13 views

Left and right derivation of Turing Machine

How can the result of the execution of $ \rightarrow RL$ differ from that of $\rightarrow LR$? In turing machines
user avatar
0 votes
1 answer
31 views

When is a grammar ambiguous or When is a grammar not ambiguous?

I was looking at an example of grammar from the website: grammer example which is as follows: S → aB / bA S → aS / bAA / a B → bS / aBB / b I believe they forgot to write: A -> a Next, we are going ...
user avatar
2 votes
1 answer
61 views

Why is this equality about the relative translation in the iterative closest point (ICP) algorithm obvious, and how can I derive it?

I'm a computer science bachelor student tasked with understanding On the ICP Algorithm by Esther Ezra, Micha Sharir, and Alon Efrat, and I'm having a lot of difficulty with even supposedly obvious ...
user avatar
0 votes
1 answer
306 views

Can a grammar that has only one leftmost derivation tree for every sentence, have more than one rightmost derivation tree for some sentence?

I'm currently studying the book Engineering a Compiler by Keith Cooper, and in chapter 3, there is the following definition: A grammar G is ambiguous if some sentence in L(G) has more than one ...
user avatar
1 vote
0 answers
34 views

How to calculate image gradient with respect to homogeneous coordinate vector?

I want to use the direct method of computing the homography between two images to estimate the plane parameters (normal and depth [= distance from camera]) of a 3D plane. If we have two images of the ...
user avatar
  • 121
1 vote
1 answer
276 views

Binary cross Entropy derivative?

I am just learning backpropagation algorithm for NN and currently I am stuck with the right derivative of Binary Cross Entropy as loss function. Here it is: ...
user avatar
  • 11
0 votes
1 answer
503 views

How to derive the worst case time complexity of Heapify algorithm?

I would like to know how to derive the time complexity for the Heapify Algorithm for Heap Data Structure. I am asking this question in the light of the book "Fundamentals of Computer Algorithms&...
user avatar
0 votes
1 answer
133 views

How should I understand left/right derivations of grammars and parse trees?

I'm having a hard time understanding how left/right derivations work. I have a very simple example that I've attempted but I don't really know how to check if it's correct. $S \to NP$ $V$ $NP$ $NP \to$...
user avatar
  • 101
1 vote
1 answer
38 views

Use or Importance of $\Rightarrow^*$ operator

Particularly, there are 2 variants of $\Rightarrow$, one is $\Rightarrow^*$ and another is $\Rightarrow^+$ which are used in derivation of strings using the productions of the grammar. As stated here,...
user avatar
2 votes
0 answers
27 views

Simple back propagation example

Sorry if this is too simplistic of a question, but over the last couple of months I have been working through the course mathematical foundations of machine learning at my college. I think I am really ...
user avatar
1 vote
1 answer
24 views

Variable derives itself

In Sipser's Introduction to the theory of computation (3rd edition), I found the following claim. Consider the grammar: $$ \begin{align*} &R \to XRX \mid S \\ &S \to aTb \mid bTa \\ &T \...
user avatar
2 votes
1 answer
36 views

When and what must be present on the left-hand side of the turnstile in metalogics?

Let me show the problem on an example... An actual task from one of the former exams: Consider a simple functional language: $$e::= x|n|e_1e_2|\lambda x.e$$ With typing rules: $$\tau ::= \mathtt{int} ...
user avatar
  • 179
0 votes
0 answers
233 views

The rightmost derivation is possible with the same rule of leftmost derivation

Can someone please help me in understanding the statement. What does it exactly mean? What I think it means is that: the derivation produces by the leftmost derivation is also possible with rightmost ...
user avatar