Questions tagged [formal-grammars]
Questions about formal grammars, generative descriptions of formal languages.
1,251
questions
76
votes
1
answer
15k
views
Language theoretic comparison of LL and LR grammars
People often say that LR(k) parsers are more powerful than LL(k) parsers. These statements are vague most of the time; in particular, should we compare the classes for a fixed $k$ or the union over ...
- 72k
40
votes
2
answers
6k
views
Are there inherently ambiguous and deterministic context-free languages?
Let us call a context-free language deterministic if and only if it can be accepted by a deterministic push-down automaton, and nondeterministic otherwise.
Let us call a context-free language ...
- 12.8k
37
votes
2
answers
5k
views
What does "context" in "context-free grammar" refer to?
There are lots of definitions online about what a Context-Free Grammar is, but nothing I find is satisfying my primary trouble:
What context is it free of?
To investigate, I Googled "context ...
- 2,957
35
votes
9
answers
4k
views
What is the significance of context-sensitive (Type 1) languages?
Seeing that in the Chomsky Hierarchy Type 3 languages can be recognised by a state machine with no external memory (i.e., a finite automaton), Type 2 by a state machine with a single stack (i.e. a ...
- 1,755
32
votes
4
answers
31k
views
How to prove that a grammar is unambiguous?
My problem is how can I prove that a grammar is unambiguous?
I have the following grammar:
$$S
→ statement
∣ \mbox{if } expression \mbox{ then } S
∣ \mbox{if } expression \mbox{ then } S \mbox{ else } ...
- 521
29
votes
3
answers
3k
views
What's really meant by context-free in the term context-free grammar?
I have been studying compilers for a while, and I have been searching what's meant by "context" in grammar and what it means for grammar to be "context-free", but with no result.
So can anyone help ...
- 401
28
votes
2
answers
46k
views
How to prove that a language is context-free?
There are many techniques to prove that a language is not context-free, but how do I prove that a language is context-free?
What techniques are there to prove this? Obviously, one way is to exhibit ...
D.W.♦
- 156k
25
votes
2
answers
29k
views
Is the complement of { ww | ... } context-free?
Define the language $L$ as $L = \{a, b\}^* - \{ww\mid w \in \{a, b\}^*\}$. In other words, $L$ contains the words that cannot be expressed as some word repeated twice. Is $L$ context-free or not?
I'...
- 741
25
votes
1
answer
9k
views
How to show that L = L(G)?
Specifying formal languages by giving formal grammars is a frequent task: we need grammars not only to describe languages, but also to parse them, or even do proper science. In all cases, it is ...
- 72k
23
votes
1
answer
417
views
Is there any nongeneral CFG parsing algorithm that recognises EPAL?
EPAL, the language of even palindromes, is defined as the language generated by the following unambiguous context-free grammar:
$S \rightarrow a a$
$S \rightarrow b b$
$S \rightarrow a S a$
$S \...
- 9,036
22
votes
4
answers
19k
views
Why is left recursion bad?
In compiler design, why should left recursion be eliminated in grammars? I am reading that it is because it can cause an infinite recursion, but is it not true for a right recursive grammar as well?
user56833
22
votes
4
answers
2k
views
Are there other ways to describe formal languages other than grammars?
I'm looking for mathematical theories that deal with describing formal languages (set of strings) in general and not just grammar hierarchies.
- 323
20
votes
1
answer
35k
views
Intersection of context free with regular languages
The intersection of a context free language L with a regular language M, is said to be always context free. I understood the cross product construction proof, but I still don't get why it is context ...
- 399
20
votes
2
answers
3k
views
What is an IELR(1)-parser?
I try to teach myself the usage of bison. The manpage bison(1) says about bison:
Generate a deterministic LR or generalized LR (GLR) parser employing LALR(1), IELR(1), or canonical LR(1) parser ...
- 876
19
votes
2
answers
2k
views
Can there be 'dead states' in a context-free grammar?
Can a context-free grammar include "dead states" from an automaton, such as
$$G = \big(\{a, b, c\}, \{A, B, C\}, \{A\to aB, B\to b, B\to C, C\to cC\}, A\big)\,?$$
The production rules $B\to C$ and $...
- 293
19
votes
1
answer
2k
views
Is language equality for linear context-free grammars decidable?
Let's consider two context-free grammars $G_1$ and $G_2$ and ask the following question: Is $L(G_1) = L(G_2)$, that is, are the two grammars equivalent?
In general, this problem is undecidable. ...
user51117
19
votes
2
answers
5k
views
How can I convert the Turing machine the recognizes language $L$ into an unrestricted grammar?
According to this Wikipedia article, unrestricted grammars are equivalent to Turing machines. The article notes that I can convert any Turing machine into an unrestricted grammar, but it only shows ...
- 375
17
votes
2
answers
4k
views
Removing left-recursion in grammar while maintaining left-association of operator
I have a problem with this exercise:
Let G be the following ambiguous grammar for the λ-calculus:
E → v | λv.E | EE | (E)
where E is the single non-...
- 173
17
votes
3
answers
3k
views
Decidable non-context-sensitive languages
It is arguable that most languages created to describe everyday problems are context-sensitives. In the other hand, it is possible and not hard to find some languages that are not recursive or even ...
16
votes
3
answers
2k
views
What would you get if you add parameters to context free grammars?
I was thinking of grammars for indendation-sensitive languages and it looks like CF grammars would do the trick if combined with parameters. As an example, consider this fragment for simplified Python ...
- 285
16
votes
2
answers
5k
views
Are regular expressions $LR(k)$?
If I have a Type 3 Grammar, it can be represented on a pushdown automaton (without doing any operation on the stack) so I can represent regular expressions by using context free languages. But can I ...
- 355
15
votes
4
answers
5k
views
Can someone give a simple but non-toy example of a context-sensitive grammar?
I'm trying to understand context-sensitive grammars.
I understand why languages like
$\{ww \mid w \in A^*\}$
$\{a^n b^n c^n \mid n\in\mathbb{N}\}$
are not context free, but what I'd like ...
- 1,287
15
votes
5
answers
6k
views
How is non-ambuiguity different from determinism?
I am trying to understand what is meant by "deterministic" in expressions such as "deterministic context-free grammar". (There are more deterministic "things" in this field). I would appreciate an ...
- 1,378
15
votes
2
answers
1k
views
Are the Before and After sets for context-free grammars always context-free?
Let $G$ be a context-free grammar. A string of terminals and nonterminals of $G$ is said to be a sentential form of $G$ if you can obtain it by applying productions of $G$ zero or more times to the ...
- 9,036
15
votes
2
answers
823
views
Is the language of words that are unbalanced in the first half context-free?
(Practice exam question in computational models)
Definition: A word $w\in \{0,1\}^*$ is called balanced if it contains the same number of $0$s as $1$s.
Let $L = \{w\in \{0,1\}^*\mid |w|$ is even and ...
14
votes
2
answers
3k
views
How did the word "production" end up being a synonym with the word "rule" in the context of Computer Science?
I am studying formal languages and production bases systems (rule-bases systems) and I am a little confused about why do these two word "production" and "rule" mean the same thing in so many context ...
- 818
14
votes
1
answer
16k
views
Difference between regular expression and grammar in automata
I am new to automata, and I have been given a brief introduction to regular expressions only yesterday. I have read the various rules which to define a regular expression. But I am unable to ...
- 143
14
votes
1
answer
264
views
When did $LR(k)$ acquire the meaning "left-to-right scan, rightmost derivation?"
According to the Wikipedia article, the L in $LR(k)$ means "left-to-right scan", and the "R" means "rightmost derivation." However, in Knuth's original paper on $LR(k)$ grammars, he defines $LR(k)$ (...
- 9,037
13
votes
3
answers
16k
views
The importance of normal forms like Chomsky normal form for CFGs
I understand that context-free grammars can be used to represent context-free languages.It might have ambiguities. We also have normal forms like Chomsky and Greibach normal form. I couldn't ...
- 2,181
13
votes
3
answers
37k
views
How is this grammar LL(1)?
This is a question from the Dragon Book. This is the grammar:
$S \to AaAb \mid BbBa $
$A \to \varepsilon$
$B \to \varepsilon$
The question asks how to show that it is LL(1) but not SLR(1).
...
- 457
13
votes
2
answers
6k
views
Is there any way to distinguish between LL(k) and LR(k) grammar?
I am recently studying about Compilers designing. I came to know about two types of grammar one is LL grammar and other is LR grammar.
We also know the facts that every LL grammar is LR that is LL ...
- 359
13
votes
2
answers
3k
views
Are all context-sensitive languages decidable?
I was going through the Wikipedia definition of context-sensitive language and I found this:
Each category of languages is a proper subset of the category directly above it. Any automaton and any ...
- 563
12
votes
2
answers
558
views
What is the closure of context-free languages under finite intersections?
Famously the intersection of context-free languages need not be context-free. On the other hand the intersection of context-sensitive languages is context-sensitive.
So this leads to the question: ...
- 121
12
votes
2
answers
11k
views
Finding the language generated by a context-free grammar
This is a question from the Dragon book (I apologize for translation mistakes, I don´t have the English version on hand):
What language is generated by this grammar?
$S \rightarrow a S b S \mid b S a ...
- 223
12
votes
1
answer
4k
views
Example of unrestricted grammar which produces non-context-sensitive language
I'm talking about Type-0 (Chomsky hierarchy) unrestricted grammar, where production rules of grammar are of the form $\alpha\rightarrow\beta$, where $\alpha,\beta\in N\cup\Sigma$.
I can not find any ...
- 345
11
votes
4
answers
10k
views
Recursive descent parser with backtracking for the grammar $S \rightarrow aSa\ |\ aa$
Can someone enlighten me why a recursive descent parser with backtracking that tries the productions $S \rightarrow aSa$ and $S \rightarrow aa$ (in that order) does not recognize the language formed ...
- 143
11
votes
2
answers
6k
views
How can I prove this language is not context-free?
I have the following language
$\qquad \{0^i 1^j 2^k \mid 0 \leq i \leq j \leq k\}$
I am trying to determine which Chomsky language class it fits into. I can see how it could be made using a context-...
- 435
11
votes
3
answers
2k
views
Decidable languages and unrestricted grammars?
Turing machines and unrestricted grammars are two different formalisms that define the RE languages. Some RE languages are decidable, but not all are.
We can define the decidable languages with ...
- 9,037
10
votes
3
answers
2k
views
Representing "but not" in formal grammar
I just came across the following grammar definition:
CommentChar ::
SourceCharacter but not LineTerminator
But for discussion, I'll present this similar ...
- 201
10
votes
5
answers
2k
views
Is there a known method for constructing a grammar given a finite set of finite strings?
From my reading it seems that most grammars are concerned with generating an infinite number of strings. What if you worked the other way around?
If given n strings of m length, it should be possible ...
- 260
10
votes
2
answers
11k
views
Is it decidable whether a given context free grammar generates an infinite number of strings?
Is the decision problem "Does a given context free grammar generate an infinite number of strings" decidable? In order to test whether a context free grammar generates an infinite number of strings or ...
- 509
10
votes
1
answer
84k
views
Different between left-most and right-most derivation [duplicate]
I am a beginner started learning theoretical computer science. I just came through context-free grammars.
So my question is: what is the different between left-most and right-most derivation?
...
- 111
10
votes
1
answer
12k
views
Relation between simple and regular grammars
I am reading "An Introduction to Formal Languages and Automata" written by Peter Linz and after reading the first five chapters I face below problem with
simple and regular (especially right linear) ...
- 203
10
votes
1
answer
476
views
Given a string and a CFG, what characters can follow the string (in the sentential forms of the CFG)?
Let $\Sigma$ be the set of terminal and $N$ the set of non-terminal symbols of some context-free grammar $G$.
Say I have a string $a \in (\Sigma \cup N)^+$ such that $x a y \in \mathcal{S}(G)$ where $...
- 203
10
votes
1
answer
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 ...
- 233
9
votes
2
answers
2k
views
Correct name for a recursive descent parser that uses loops to handle left recursion?
This grammar is left recursive:
...
- 91
9
votes
1
answer
20k
views
Left recursion and left factoring -- which one goes first?
if I have a grammar having a production that contains both left recursion and left factoring like
$\qquad \displaystyle F \to FBa \mid cDS \mid c$
which one has priority, left recursion or left ...
- 355
9
votes
1
answer
1k
views
Arithmetic expressions grammar transformation
In the article Parsing Expressions by Recursive Descent by Theodore Norvell (1999) the author starts with the following grammar for arithmetic expressions:
...
- 290
9
votes
2
answers
2k
views
Is there a different resolution of the "dangling else" problem other than "match closest"?
The following context-free grammar presents a "dangling else" type ambiguity (imagine that $a$ stands for if expr then and $b$ stands for ...
- 318
9
votes
1
answer
788
views
How powerful are CFGs that allow an infinite number of rules?
I was wondering recently what would happen if we'd allow context-free grammars to have an infinite number of rules. Clearly, if we'd allow arbitrary such infinite sets of rules, every language $L$ ...
- 401