Questions tagged [derivation]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
11 views

Confusion on the use of the chain-rule for the total derivative of the NLL Loss function

So my question is about when we want to find the total derivative of the NLL Loss function $L$ w.r.t. $w_i$. So the "pipeline" is often expressed as: $$\frac{\partial L}{\partial w_i} = \...
ZenPyro's user avatar
  • 23
0 votes
1 answer
264 views

Find the language generated by the Context Free Grammar

I am trying to find the language generated by this context-free grammar S → aSb | bbY | Yaa Y → bY | aY | ε I understand that one way to solve is this to find set ...
Mahesh Jamdade's user avatar
0 votes
1 answer
105 views

Greibach Normal Form: Proof every sentential form is of the form xy with x terminals and y variables

For any grammar in Greibach normal form, every sentential form obtained from S by a partial left-most derivation is of the form xy with x terminals and y variables. I think that this can be proven ...
Ronald's user avatar
  • 89
-2 votes
1 answer
70 views

proof that every sentence obtainable by left-most derivations only when Greibach normal form

Could someone help me prove the following statement: “For any grammar in Greibach normal form, every sentence is obtainable by left-most derivations only.” I see that this is trivial, but I can't ...
Tryer outer's user avatar
0 votes
0 answers
18 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
Miguel JV's user avatar
0 votes
1 answer
1k 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 ...
Pratik Hadawale's user avatar
2 votes
1 answer
69 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 ...
Mandelmus100's user avatar
0 votes
1 answer
1k 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 ...
Angelo Marcelino's user avatar
1 vote
0 answers
64 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 ...
jiggy's user avatar
  • 121
1 vote
1 answer
523 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: ...
Paul G.'s user avatar
  • 11
0 votes
1 answer
863 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&...
Midhunraj R Pillai's user avatar
0 votes
1 answer
214 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$...
AFC's user avatar
  • 101
1 vote
1 answer
39 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,...
Perspicacious's user avatar
2 votes
0 answers
28 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 ...
lmurdock12's user avatar
1 vote
1 answer
43 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 \...
user9515151's user avatar
2 votes
1 answer
41 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} ...
gaazkam's user avatar
  • 179
0 votes
0 answers
265 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 ...
Faizan Khan's user avatar