# Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

1,251 questions
Filter by
Sorted by
Tagged with
129 views

### Stuck on Converting to Chomsky Normal Form,

I am supposed to be changing this to Chomsky Normal Form and then to Greibach form, but I am still having a few difficulties changing it to the first form. Here is the language: S → AA|SBBa|b A → ...
1 vote
555 views

### CFG for the language {w ∈ {0, 1}∗ : w is a palindrome and |w| is divisible by 3}

The question is the following: Construct CFG for the L = {w ∈ {0, 1}∗ : w is a palindrome and |w| is divisible by 3}. I am able to construct CFG for the set of all palindromes as below: S --> aSa | ...
1 vote
38 views

### Communication complexity of Dyck language

I've been reading papers on streaming algorithms and ran across the following question which I haven't been able to answer: Consider the Dyck language $Dyck(2)$ over the alphabet $A = \{(,),[,]\}$ and ...
1 vote
15 views

### Number of DCFG parse tree nodes with respect to input length

I read the question and answer at Number of nodes of a parse tree when the Grammar is in CNF?, and I'm curious about a related matter: obviously with a unrestrained LR grammar (as opposed to CNF) the ...
651 views

### Is the language $L = \{0^i 1^j | i \ne 2j\}$ context free?

I have been trying to find a a CFG for this language generated. I came to the conclusion that I need three parts When $i \le j$ When $j < 2j < i$ When $j < i < 2j$ I was able to come up ...
48 views

### Derivation trees to show a given grammar is ambiguous

Given the grammar with productions: \begin{align} S \rightarrow aSb \mid SS \mid \lambda\\ \end{align} I would like to show that it is ambiguous. As I understand it, if you can show that some string ...
1 vote
370 views

### How to prove that this "priority" strategy (in ANTLR4) solves the "dangling-else" ambiguity?

As shown in this post @ stackoverflow, ANTLR4 seems able to resolve the "dangling-else" ambiguity @ wiki in the following "if-then-else" grammar by prioritizing the "...
118 views

256 views

### How to design a formal grammar to convert EBNF description to a list of CFG production rules

I would like to write a grammar to convert EBNF description to a list of CFG production rules, instead of an algorithm. Can CFG production rules is generated from an EBNF description by a rewrite ...
37 views

### The language of chains with twice as many $a$s as $b$s is regular?

I am trying to understand the pumping lemma and its instrumentation to show a certain language is not regular. My first attempt was the following problem: Let $L$ be the language of all words that ...
451 views

### Shift-resolve parsing - questions

I've recently came across a paper describing the parsing technique mentioned in the title. Unfortunately, the terminology used in said paper is somewhat beyond my comprehension, so I've been ...
135 views

### Generating a recursive descent parser for grammar having Kleene star

From what I have been taught, I cannot use left-recursive, nondeterministic, or ambiguous grammars in recursive descent parsers. So, here is the grammar: \begin{align} &E \to E+T \mid T \\ &T \...
57 views

### Is { a^nb^na^n} a context-sensitive language?

The language $L_1 = \{ a^nb^nc^n \}$ is often given as an example of a context-sensitive language. I am wondering if the language $L_2 = \{ a^nb^na^n \}$ belongs also to the same category?
44 views

### Doubt in pumping lema for context-free language

I have a doubt related to pumping lemma in CFL for which I dont find an answer, so I think is very easy because no one wonder about. The lemma says: My doubt is: Is there any restriction related to ...
1 vote
367 views

### Negative lookahead in LR parsing algorithm

Consider such a rule in grammar for an LR-family parsing generator (e.g YACC, BISON, etc.): Nonterminal : [ lookahead not in {Terminal1, ..., TerminalN} ] Rule ; ...
148 views

### How do I represent this regular expression in regular grammar?

Question: Is the regular expression and regular grammar equivalent? I've look on some examples of regular grammar however I don't think I fully understand how to convert regular expression to its ...
610 views

...
7k views

### Converting CNF to GNF

I'm studying context free grammars and I can grasp how to create context free grammars given a set notation, and now to convert these context free grammars to Chomsky Normal form but I am utterly ...
1 vote
31 views

### What is a formal grammar equivalent to one-way stack automaton?

As the title says, is there a formal grammar characterization of the class of one-way stack languages?
34 views

### Nonterminal Complexity of a context-free grammar

Suppose $G$ is a CFG. $G = (N, T, P, S)$, $Var(G)$ as the cardinality of $N$ $Var(L)$= min {$Var(G)$ | G is a context-free grammar and $L(G) = L$}. I have a problem in understanding a part of proof ...
18 views

### Decide if complement of context-free language is also a context-free language

Consider the following grammar $G$: $$S \rightarrow SA \ | \ AS \ | \ aXb \ | \ bXa, \ \ \ X \rightarrow \# \ | \ BXB, \ \ \ A \rightarrow a \ | \ b \ | \ \#, \ \ \ B \rightarrow a \ | \ b$$ Decide if ...
2k views

### Is a machine Turing-complete when it can decide a context-sensitive language?

If a machine can decide a context-sensitive language (like the language of palindromes with a non-linear center) is that fact a proof that the machine is Turing-complete? Can this be used to prove ...
79 views

### Is this grammar LL(1) and what is it's parsing table?

Let G be a grammar with non-terminal A, terminal a and these productions: A -> A a It is ...
1 vote
32 views

### Equivalence of LR(k) and LL(k′) parsers

Are there languages that can be parsed by an LR(k) parser but not by an LL(k′) parser for any k′?
50 views

### Removing null production from cfg

While removing null production from cfg as below, S->ABC A->aA|^ B->bB|^ C->aaC|^ now as shown above we know that A,B and C all are ...