# Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

1,054 questions
Filter by
Sorted by
Tagged with
19 views

### How do you create a sentential form in a given grammar?

I am given the following grammar: $$S ::= aBS| abT |a$$ $$T::= d | dT$$$$B ::= da | ϵ | S$$ I need to decide whether $aBaabda$ can be produced in the given grammar. I am unsure how the grammar can ...
12 views

### Having trouble understanding how to prove a language context free? [duplicate]

I've been studying the theory of automata. I came across this problem in the book and unable to understand how to solve this. I've solved some examples using the Pumping lemma but this one uses ...
20 views

27 views

### Converting a regular expression to a grammar and regular grammar

I am working on a pretty small lab for my university course and I'm having trouble converting a given regex into a set of regular definitions, then into a grammar and finally a regular grammar. I have ...
13 views

### What's the context-free grammar for { w | 2*(number of a's in w) != 3*(number of b's in w) +2 }? [duplicate]

So I have this language: $$A= \{ w \in \{a,b\}^* \mid 2*\#_a(w) \ne 3*\#b(w) + 2\}$$ I know it's context free, I know how to make a PDA for it, I just can't, for the life of me, figure out how to ...
16 views

### Show {𝑎^i𝑏^j𝑐^k, i!=j!=k} is context free or not, how can we prove it? [duplicate]

I stuck on this question for a long time and cannot figure out how to prove it?
23 views

### Show {𝑎^i𝑏^j𝑐^k, 𝑖!= j and 𝑗 != 𝑘} is a context-sensitive language, what is the grammar? It is context free or nor?

I've been pondering this question for a long time, that 𝑎^i𝑏^j𝑐^k, 𝑖!=j and 𝑗 != 𝑘 is a context-sensitive language, how we can prove it to be context sensitive or which grammar can generate such ...
616 views

### Is every unambiguous grammar regular?

While searching for an answer to this question I found out that there is an unambiguous grammar for every regular language. But is there a regular language for every unambiguous grammar? How can I ...
45 views

### a^ib^jc^k, i < j < k is a context-sensitive language, how can prove it as a context sensitive

I've been pondering this question for a long time, that $a^ib^jc^k, i < j < k$ is a context-sensitive language, how we can prove it to be context sensitive or which grammar can generate such a ...
18 views

### Do the SLR and LALR parsers of a same CF grammar have the same shift actions?

In theory, given that: The LALR parser can be constructed by merging LR(1) states with the same core; If $I$ is a LR(1) set of items, then $\text{core}(\text{GOTO}(I))=\text{GOTO}(\text{core}(I))$; ...
23 views

### ANTLR G4 grammer for math expression

I am new to grammar and have written grammar for parsing math expression for asciiMath using ANTLR as below. ...
29 views

### Constant single match regex

I am looking for the name (definition?) of X in: A regular expression is X iff it has exactly one possible match. Examples: <empty regex>, abc, ...
21 views

### Use of graph grammars/rewriting systems in compilers?

A(n imperative) program - in a higher-level language and more importantly in assembly language or intermediate representations like LLVM - can be formalized as a directed "port graph", in ...
46 views

### How to write “∀x.F(x)” for “F(x)=λx.Φ(x)” in one expression (sequel from question about “∀(λφ. (φ x m→ φ y))”?

This question is sequel from How to understand quantifier without predication " ∀(λφ. (φ x m→ φ y))"? which further explains the notation and context. So - I have anonymous Boolean-valued ...
39 views

### Is this grammar in Backus–Naur form?

I'm a newbie and a paper I'm reading specifies the following grammar: ...
60 views

79 views

### Enumerator for Word and Halting Problem

in theoretical computer science I learned for every recursive enumerable language there would be an enumerator and a grammar. So since word problem and halting problem are recursively enumerable, I ...
49 views

### Is there a way to map the concatenation operation over strings to the addition operation over $\mathbb{N}$

Given an alphabet, say $\Sigma = \{0,1\}$, I can make a one-to-one mapping from all possible strings $x \in \Sigma^*$ to $\mathbb{N}$. This could be done by ordering $\Sigma^*$ lexicographically and ...
78 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

### What is a make sense (meaningful) example of language that an unrestricted grammar could generate?

I have learned that: Unrestricted grammar is used to define (or describe) a formal language. Unrestricted grammar is used to define recursively enumerable set [https://en.wikipedia.org/wiki/...
39 views

### Turning grammar to LL(1)

I have difficulty / doubt in transforming a grammar into LL (1), I tried remove left recursion but grammar still not LL(1). ...
48 views

### Help with context free grammar excercise

So, I have an exercise in which I have to write a context free grammar for this language: $$L = \{x \in L(a^∗b^∗c^∗) : |x|_a > |x|_c; |x|_b > 0; |x|_c ≥ 0\}$$ meaning every string with any ...
25 views

### Is there any good method to find if a grammar is optimal for a problem?

I've been thinking about grammatical evolution problems and how the grammar influences the algorithm performance. It came to my mind the huge impact that the grammar that you're using has in the time ...
37 views

### removing indirect left recursion

I want to remove indirect left recursion from these rules: S-->TU, T-->US|b, U-->ST|a I don't know if I can implement the algorithm correctly. ...
44 views

### Are there context free grammars for all restricted Dyck paths?

A Dyck path is a finite list of $1$'s and $-1$'s whose partial sums are nonnegative and whose total sum is $0$. For example, [1, 1, -1, -1] is a Dyck path. Rather ...
54 views

58 views

### What does it take to create a new programming language and its toolchain?

I am super novice to this topic, so my apologies if my question looks completely nonsense to you all! Imagine you want to create a new programing language that transpiles to a more common high/low-...
26 views

### Upper bound on size of derivation in CFG

Suppose $G$ is a $CFG$ with $m$ variables, in which the right-hand side of all production rules has length at most $\ell$. Show that if $A\Rightarrow^*_G\varepsilon$, then there is a derivation of no ...
434 views

### What are the modern alternatives to Backus–Naur form and what are their advantages?

I am very new to the whole concept of context-free grammars to represent the syntax tree of formal languages (i.e., programming languages). It seems that the Backus–Naur form (BNF) is the oldest of ...
202 views

### What are the known ambiguities in C language grammar?

I have found this reference for the C syntax Backus-Naur Form (BNF). I was wondering if there are any other ambiguities in this grammar other than the infamous "dangling else"? Also how we ...
18 views

### Predicitve Parser LL(1) condition

Lets say we use the predictive parser LL(1). Why is it necessary that $FIRST(\alpha) \cap FIRST(\beta) = \emptyset$, for all $\alpha, \beta$ right side of alternative productions i.e., productions ...