Questions tagged [formal-grammars]
Questions about formal grammars, generative descriptions of formal languages.
1,056
questions
0
votes
0answers
19 views
Building Context sensitive grammars?
I just discovered Context-sensitive grammars.
The problem is most of the examples are weird non-interesting toy languages !
Second the descriptions are math oriented, rather than programmer oriented.
...
-1
votes
0answers
11 views
What does the number in the brackets represent in parsing techniques, such as LL(1), LR(0), etc.?
I am studying language compilers and grammars, and I can't seem to tell what the numbers represent in the brackets of the different parsing techniques.
And as a side question (no need to answer): what ...
0
votes
0answers
18 views
Parsing a context free grammar, Backus Naur question
Does anyone know how BNF rules expecting the empty string ($\epsilon$ or the "") behave during creation of a parse tree using grammar from a string of ...
1
vote
1answer
536 views
What does it mean for a grammar to be LR(0)?
I am unsure what it means for a grammar to be $X$. More specifically, what it means for a grammar to be LR(0).
For part of an assignment I had to form the DFA for a grammar, which I had no issues with....
2
votes
1answer
53 views
How can I show that this language is context sensitive?
I have this language $L=\{a^nb^nc^n,n\geq0\}$, I know this language is not context free, but I don't know how to show that it is context sensitive, do I have to use a PDA?
0
votes
1answer
29 views
Formal proof of language accepted by a specific CFG
Let $G=(V,\Sigma,R,S)$ be the grammar given by the following rules:
\begin{align}
&S \to aS \mid B \\
&B \to abBc \mid \epsilon
\end{align}
Please provide a formal proof for the following ...
1
vote
1answer
37 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 ...
0
votes
0answers
14 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 ...
1
vote
1answer
28 views
How can we generate a grammar for $\{a^n b^n c^n d^n; n > 0\}$ if it is NOT context free?
This page on Wiki states that $\{a^nb^nc^nd^n \ | \ n > 0\}$ can not be generated by a CFG. This does not make sense to me as $\{$S $\to$ ABCD, A $\to$ aA | a, B $\to$ bB | b, C $\to$ cC | c, D $\...
0
votes
0answers
18 views
CFG for the language x^n y^m, where n ≥ 1, m ≥ 1, and n ≠ m [duplicate]
Can anyone help me construct a CFG for this? It really has me stuck for some reason.
0
votes
1answer
16 views
Are these production rules for a formal grammar?
I have a question on if production rules of a formal grammar are being specified correctly. Wikipedia defines the syntax of grammars as the following finite set of production rules, where it states ...
-1
votes
1answer
37 views
Transform grammar to Chomsky Normal Form
Question:
S → abSab | baSba | TT
T → aTa| bTb | ε
My answer:
Eliminate ε rules:
S-> abSab | baSba | TT | T
T-> aTa | bTb | aa | bb
Correct answer:
S → abSab | baSba | TT | abab | baba | T
T → ...
0
votes
2answers
28 views
How to tell if a grammar is LALR(1) formally?
There is an “informal” definition of $\operatorname{LR}(k)$ (can be recognised by a parser that looks at $k$ symbols ahead) and a “formal” one (as a property of the set of rightmost derivations ...
0
votes
2answers
63 views
How do Context Sensitive Grammar systems work?
The Quest: Use context sensitive grammar (CSG) to produce an equal N number of repeating a, b, and c using the alphabet {a, b, c}. For example, if N = 5 use CSG and a, b, and c to produce a result ...
1
vote
1answer
108 views
Linear Grammar in less than cubic time
I have a linear grammar $G$ and a string $s$. $G$ is is not limited to right or left linear only but rather has a mix of rules of both types.
Is there an algorithm to determine whether $s \in L(G)$ ...
2
votes
1answer
36 views
Is “A -> aAA” convertible to regular grammar?
I have a simple grammar as below and wonder if it is convertible to regular grammar?
If yes, what is the conversion sequence? If no, how can we prove it?
...
1
vote
1answer
22 views
How to find the language of a CFG from Production rules
I'm having problems in finding language of the CFG from given production rules. For example if the production rules are
\begin{align}
&S \to AS \mid \epsilon \\
&A \to aa \mid ab \mid ba \mid ...
6
votes
1answer
349 views
What are the closure properties of LL(k) languages?
Suppose I have two LL languages $L_1, L_2$, both describable by LL($k$) grammars for the same $k$, and regular language $R$. Which of the following are also LL languages, and can they be described by ...
0
votes
1answer
25 views
left/right derivations of grammars and parse trees
I'm having a hard time understanding how left/right derivations work. I have a very simple example that I've attempted but I don't really know how to check if it's correct.
$S-> NP$ $V$ $NP$
$NP -&...
0
votes
0answers
31 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 ...
0
votes
0answers
14 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 ...
0
votes
0answers
17 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?
0
votes
0answers
25 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 ...
4
votes
1answer
618 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 ...
0
votes
0answers
49 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 ...
0
votes
0answers
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))$;
...
0
votes
0answers
26 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.
...
0
votes
0answers
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, ...
0
votes
0answers
23 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 ...
1
vote
0answers
47 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 ...
0
votes
0answers
40 views
Is this grammar in Backus–Naur form?
I'm a newbie and a paper I'm reading specifies the following grammar:
...
0
votes
1answer
75 views
Converting PDA to CFG
I am trying to understand this example of converting PDA to CFG but I am not getting the idea quite right. I do have the general understanding of theorem that if $p,q\ \epsilon\ Q $ and $X \varepsilon\...
1
vote
0answers
53 views
Is every language described by a grammar?
I read the following argument showing that not every language is described by a grammar:
For a fixed alphabet $\Sigma$ and variables $V$ there are uncountable many languages over $\Sigma$ since the ...
0
votes
1answer
25 views
If a grammar G is left and right regular, why $||L(G)|| \leq ||P||$?
I was studying automata theory and formal languages and came across this question:
If a grammar $G$ is left and right regular, why $||L(G)|| \leq ||P||$ ?
I've searched the theory but I am missing ...
0
votes
1answer
43 views
Is there any official terminology about something like double quotes “” grammar?
In many programming language string is a token.
For example:
...
0
votes
1answer
100 views
Removing left factoring from Context-Free Grammar
I know that, removing left factoring is a simple task.
And i understand following procedure:
$S→aA | aB$
Becomes:
$S→aS'$
$S'→A|B$
Yet I'm running into problems with this particular grammar:
$S→AD|...
0
votes
1answer
85 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 ...
0
votes
1answer
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 ...
-1
votes
1answer
84 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 ...
0
votes
0answers
38 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/...
0
votes
0answers
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).
...
1
vote
1answer
49 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 ...
0
votes
0answers
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 ...
0
votes
2answers
42 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. ...
3
votes
0answers
47 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 ...
0
votes
2answers
68 views
How to remove null production from context free grammar?
How to remove null production and simply the grammar?
$$
S \to a \mid Ab \mid aBa \\ A \to b \mid \epsilon \\ B \to b \mid A
$$
Can the simplification result in this CFG?
$$
S \to a \mid aBa \\ A \to ...
-1
votes
1answer
24 views
How to simplify context free grammar?
How to simplify this context-free grammar into a similar one with no unit productions and no useless symbols?
$$
S \to ABA \\ A \to aAA \mid aBC \mid bB \\ B \to A \mid bB \mid Cb \\ C \to CC \mid cC
...
0
votes
0answers
59 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-...
0
votes
0answers
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 ...
1
vote
1answer
452 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 ...
