Computer Science

think you may have an interesting question there. never really studied subj in terms of "linear grammars" much. wikipedia defines it in terms of CFGs and says RLs are a special case.

Linear grammar

In computer science, a linear grammar is a context-free grammar that has at most one nonterminal in the right hand side of each of its productions. A linear language is a language generated by some linear grammar. == Example == A simple linear grammar is G with N = {S}, Σ = {a, b}, P with start symbol S and rules S → aSb S → ε It generates the language { a i b i | i ≥ 0 }...

> the left-linear or left regular grammars, in which all nonterminals in right hand sides are at the left ends;
> the right-linear or right regular grammars, in which all nonterminals in right hand sides are at the right ends.
> Collectively, these two special types of linear grammars are known as the regular grammars; both can describe exactly the regular languages.

that descr does not seem very clear, it seems to be talking about the left/ right sides of derivation rules?

parvin

4:57 PM

thank you @vzn

yes it is saying that there are two special cases of linear

linear is like S->aSb in which you can repeat "a" and "b" as much as you like
if there is only S->aS it is growing from left side (is : aS,aaS,aaaS,aaaaaaS,...)

if it is like S->Sb it is growing from right side (is: Sb,Sbb,Sbbbb,...)
and is right linear

if it's a mixture of both, it is only called linear. non of the special cases

i'm trying to read the book (linz-automata thory) chapter 4 to find out if I can change left linear to right linear

(converting two special cases)

2 hours later…

Bounty!

7:21 PM

-1

Q: How to find max flow in a graph after incrementing/decrementing an edge capacity?

We're given a graph $G=(V, E)$, with source $s$ and sink $t$, $s\neq t$, and that all capacities are non-negative integers. Also the value of max flow is given as well as some edge $e'$. How can max flow be found if we increment/decrement the capacity value of $e'$ by $1$ in linear time? I...