# Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

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

### Finding a context free grammar (CFG) for a non-context free language (CFL) a^n b^n c^n

It is known that the language $\{a^nb^nc^n|n\geq0\}$ is not context-free (we can prove it using the pumping lemma, as shown here: Is $a^n b^n c^n$ context-free?). Yet, this answer claims it has found ...
• 1
1 vote
58 views

### Constructing an unrestricted grammar for XWX, where W is the reverse of X

I'm trying to construct an unrestricted grammar for strings of the form XWX, where W is the reverse of X, over the alphabet {a, b}. I think I can apply similar logic to the a^nb^nc^n solution (below), ...
346 views

### How to identify Context-Sensitive Grammar?

Context-Sensitive Grammar is defined as a 4 tuple G = (V, Σ, R, S) where: V is a finite set of elements known as variables. Σ is a finite set of elements known as terminals V ∩ Σ = Null (empty set) S ...
• 25
1 vote
292 views

• 141
330 views

### How to find context sensitive grammar for words like ww?

I'm studying formal languages and automata, and on the section of learning how to find productions that generates the grammar, I've done some exercises pretty well and was able to do some of the ...
75 views

### How would my parsing functions look for this grammar?

Suppose we have the grammar $$S \to aA | BA$$ $$A \to a | bB | \epsilon$$ $$B \to cB | d$$ I know that I need to write four different functions in order to parse this grammar. They are ...
• 3
325 views

### LALR(1) grammar for simple math parser

I am trying to write a simple parser for a small calculator project, that should be able to parse e.g. the following inputs: ...
• 33
82 views

### Decidability of a given grammar if it is regular

According to my course the question "Is $L(G)$ regular?" undecidable. But I was more interested in knowing the exact algorithm or proof that makes this question undecidable. To further ...
30 views

### Is there a context-agnostic concept of automatic (log-)text parsing that supports human reader filtering out redundancy?

This question is about ideas I regularly think about, and I would like to know what concepts already exist. Also I am not sure at all if this really makes sense, by now it is just a crazy idea ...
• 131
49 views

### How to prove correctness of a bidirectional converter between two CF grammars?

I have a converter between two context-free grammars which are both describing the same language but one uses infixes other than prefixes, has different symbols and sometimes switches order of ...
• 129
140 views

### How to count the number of nodes for a tree generated by context free grammar derivation?

Given context free grammar I use breadth first search and left most derivation rule to generate all possible words for a given language. For example: ...
• 299
422 views

• 21
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 "...
• 9,501
381 views

### How does LALR(1) parser behave compared to LR(1) paser?

In Section 4.7.4 of the book "Compilers: Principles, Techniques, and Tools" (2nd Edition), it reads: "The revised parser (LALR(1)) behaves essentially like the original (LR(1)), .... ...
• 9,501
36 views

### References to deterministic time complexity of language classes

It's fairly well known that $REG \in TIME(n)$. I would like to know similar inclusions for the language classes $DCFL$ and $CFL$. I have found a variety of claims for these classes on the internet. ...
35 views

### Grammar where the precedence of condition operators are asymmetric with regard to assignment operators

In Unix shell programming, there's the ideom: program1 && program2 && program3 where successful completion of ...
• 192
58 views

### What does $g \to \lambda$ mean in the L-System for the dragon curve?

I am playing with L-System using the wonderful tool jflap. Below is the L-System for the dragon curve in the "JFLAP book: JFLAP – An Interactive Formal ...
• 9,501
141 views

### Convert a dfa to rule for a asterisk case

Here is a simple but very common grammar rule case in EBNF format, the Statements is a none terminal symbol and Statement is ...
• 19
48 views

### I can't visualize what happens when we pump v and y in pumping lemma for $a^n b^n c^n$

If you need some context-: https://www.andrew.cmu.edu/user/ko/pdfs/lecture-11.pdf around page 7. Case 1-: Say vxy contains ab So when I pump v and y, what will get pumped? And how the result would be. ...
• 37
1 vote
294 views

### CFG for L={a^i b^j c^i; i,j > 0}

I worked a bit on this and got this-: S->ABC A->aA/a B->bB/b C->cC/c The obvious problem here is I am unable to count number of a's and c's which ...
• 47
29 views

### What is the subset of CFGs called where each expansion must be the same?

I was wondering about a kind of grammar where we can expand rules of the form A -> X|Y|... with A being a nonterminal and <...
• 103