# Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

1,030 questions
Filter by
Sorted by
Tagged with
212 views

### Questions About P, NP, languages [closed]

I'm trying to get a better grasp of computation theory, and have a few questions that I can't seem to find great answers too. Given language L, which is non-recognizable, is L* context free? Is P ...
245 views

### Neither Left nor Rightmost Derivations

Consider a simple grammar and its derivations. The derivations could be done in leftmost or rightmost patterns and can also be done in no particular order as the derivation order has no effect on the ...
57 views

### Trouble understanding Grammar Rules

I am totaly new to theoretical computer science, so I am sorry if I get the terminology wrong: I was reading the definition of a grammar, what I didn't get was the formal definition of the production ...
56 views

### Why doesn't the string match the root?

From Reading 17 of 6.005 — Software Construction: Exercise Reading a Grammar 4: Which strings match the root nonterminal of this grammar? ...
690 views

### Is a regular grammar valid if it only contains production rules that have nonterminals in the right operand?

For example: S -> Sa Let's say the alphabet is {a} and that is the ONLY production rule of the grammar. Is that grammar valid regular grammar ? Or valid grammar at all? Can it be a context free ...
147 views

### How to write a regular expression to match a string that starts with the same pattern that it ends with

Let's say we want to write a regular expression that matches a string that ends with the same pattern that it begins with. Let's say that we have an alphabet composed of the binary symbols: {0,1} We ...
28 views

125 views

565 views

### How to remove empty strings a.k.a (lambda, epsilon) from a LR(0) grammar

Say I have the following grammar: E -> TE' E' -> +TE'| -TE' | λ T -> (E) | id I need to build the finite state machine with the LR(0) items, But I ...
81 views

### Is the language $\{a^{n^2-1} | n \in \mathbb{N}\}$ context free? and how to prove it? [duplicate]

Is the language $\{a^{n^2-1} | n \in \mathbb{N}\}$ context free? and how to prove it? I think it is, but I could not find a way to prove it by using push down automaton or any other way.
52 views

### Where is the ambiguity in this grammar?

I am trying to understand ambiguous grammar in programming languages. I was given this ruleset and told it was ambiguous. If my understanding is correct, this means that it is possible to create the ...
174 views

### Chomsky NF or Greibach NF benefits for LR parser?

Are there any benefits of having grammar in CNF/GNF for LR parser? I have those in mind: total speed of creating a parser (that is time for creating CNF/GNF out of the grammar, and then creating ...