6
votes
Is the emptiness problem for PEGs decidable?
I should have done my research better before asking. The original paper introducing PEGs (Parsing Expression Grammars:
A Recognition-Based Syntactic Foundation by Bryan Ford) actually contains a proof ...
- 12.3k
4
votes
Dragon book exercise 4.4.5, why is aaaaaa not recognized by the recursive descent parser?
When you look at the parser's process, you see the entire text to be parsed, and naturally make judgements based on that knowledge. But that's not the way the parser works. So your strategy makes it ...
- 11.2k
4
votes
Accepted
How to identify Context-Sensitive Grammar?
You are right: the grammar in your example is strictly speaking not context-sensitive. It is a monotonic (or non-contracting) grammar. In those grammars the main restriction is that the lefthand side ...
- 27.6k
3
votes
Accepted
Prove/Refute that $L=\{w\$x^R \ |\ x\ is\ a\ substring\ of\ w\}$ is a regular language
Suppose towards a contradiction that $L$ is regular and let $p$ be its pumping length. Consider the word $a^p\#a^p \in L$. By the pumping lemma there is some $1 \le k \le p$ such that $a^{p-k}a^{ki}\#...
- 23.4k
3
votes
Accepted
LALR(1) grammar for simple math parser
As modified by your edit, your grammar is unambiguous. Unfortunately, it is not deterministic; no limited lookahead is sufficient to decide whether when the parser reaches a comma: $$\bf{ID}\;\bf{(}\;\...
- 11.2k
3
votes
Accepted
What does $g \to \lambda$ mean in the L-System for the dragon curve?
"$\lambda$" is commonly used to represent the empty string, although "$\epsilon$" could be the more common one.
This was introduced earlier in that book, section "3.1 Grammar ...
- 34k
3
votes
Accepted
PDA with multiple element access - $i$ - access PDA
Hint: replace every $d$-depth transition with a set of states and transitions that will read out $d-1$ elements, then read the last element and do the transition, and afterwards return the last $d-1$ ...
- 10.8k
3
votes
Accepted
Find a Context-Free Grammar for $L = \{a^wb^xc^yd^z | w + x = y + z\}$
The constraints on $w, x,y, z$ are not given, I choose everyone $\geq 0.$
The strings could be equal $a$ and equal $d,$ equal $b$ and equal $c,$ equal $b$ and equal $d,$ equal $a$ and equal $c $ etc(...
- 468
3
votes
Accepted
Show that the Hamming distance of $wx$ and $xw$ cannot be 1
Lemma:
The parity of the Hamming distance between two strings is the parity of the total number of $1$s.
Proof:
If you toggle any bit in any of the strings, the parity of the distance changes. Start ...
- 3,912
2
votes
What is the formal definition of precedence and associativity in programming language?
Look at the Swift language where the available operators are not defined in the language, but in the standard library. There are rules that let the compiler distinguish between binary and unary ...
- 25.2k
2
votes
Context free grammar for strings with more $a$'s than $b$'s
Here is a somewhat simpler proof for $L \subseteq \mathcal{L}(G)$.
Apply induction directly to the claim that any string in $L$ can be generated by $G$.
As before, the base case is done by $S \...
- 196
2
votes
Accepted
Stuck with shift-reduce conflicts on yacc on grammar to generate palindromic strings on {0,1}
The grammar is, as you say, unambiguous. But it is not deterministic. LR parsers with bounded lookahead can only recognise deterministic languages; since not all unambiguous context-free languages are ...
- 11.2k
2
votes
Hierarchy of parser grammars vs Chomsky hierarchy of grammars and the comparsion of the language acceptance power of each parser grammar
All of the grammars in your first figure are context-free grammars. That text seems to identify grammar with context-free grammar.
- 270k
2
votes
CFG for L={a^i b^j c^i; i,j > 0}
So I worked a bit. And I think I got the answer. Feel free to correct me.
S -> aSc | aXc
X -> bX | b
It works a bit, e.g.: ...
- 47
2
votes
Accepted
What is the subset of CFGs called where each expansion must be the same?
Every such language is finite and regular. Basically, we can think of the grammar as working as follows: we first make a decision for each non-terminal about which way it will expand; then that ...
D.W.♦
- 141k
2
votes
Accepted
Context free grammar for $1^n 0^m 1^k 0^p$ where $n+k=m+p$
We want to generate strings of the form $1^n 0^m 1^k 0^p$ with the same number of $0$ and $1$. This language can be generated by distinguishing two cases.
The first approach is to draw a diagram what ...
- 27.6k
2
votes
2
votes
Accepted
How does LALR(1) parser behave compared to LR(1) paser?
The explanation is given in the following paragraphs. Given a correct input, the LALR parser produces exactly the same sequence of reduce and shift actions as would an LR parser for the same grammar. ...
- 11.2k
2
votes
LALR(1) grammar for simple math parser
The problem occurs with the parsing prefixes having the form f(id, id, ..., so that your grammar cannot determine by any means what do they denote: either the ...
- 565
2
votes
Accepted
Decidability of a given grammar if it is regular
Undecidability is counter-intuitive at the best of times, and proofs of undecidability might feel unsatisfying at first glance, since they are necessarily non-constructive. (How can you construct an ...
- 11.2k
2
votes
Accepted
Disambiguating grammar for Dyck language
Your language is very similar to the Dyck language, the only difference being that the Dyck language usually contains the empty string.
Here is an unambiguous grammar for your language:
$$
S \to (S)S ...
- 270k
2
votes
Finding a context free grammar (CFG) for a non-context free language (CFL) a^n b^n c^n
No. Every context-free grammar generates a context-free language. If you can find a context-free grammar for a language, then the language is context-free.
That assumes the claimed grammar is ...
D.W.♦
- 141k
2
votes
Accepted
Is THEADS the same as FIRST?
I recently had the same question in mind when reading Pager's work. I found the paper The Edge-Pushing LR(k) Algorithm by Chen and Pager, which seems to say that the two terms are indeed the same. ...
- 137
2
votes
Decidability of a context free Grammar
"Redness" is decidable, because the alphabet of a context-free grammar is finite (by definition), and therefore the set of strings exactly three characters long starting with ...
- 11.2k
2
votes
Accepted
Context-free grammar for $L=\{ a^nb^m | n \le m+3 \}$
$S \rightarrow aSb/A $
$A \rightarrow \epsilon/a/aa/aaa/B$
$B \rightarrow bB/\epsilon$
- 468
2
votes
Accepted
Prove a stronger version of the pumping lemma for context-free languages
Proof Idea for the usual pumping lemma
Let $z$ be a very long string in $L$. A parse tree for $z$ is so tall that it must contain some long path from the start symbol at the root of the tree to
one of ...
- 34k
2
votes
Show that the Hamming distance of $wx$ and $xw$ cannot be 1
$w$ and $x$ are binary strings.
Clearly $|wx|=|xw|$ and $|wx|_0=|xw|_0$. Suppose $wx$ and $xw$ differ only at position $i$, so that $(wx)[i]\ne(xw)[i]$, $(wx)[1..i-1]=(xw)[1..i-1]$, and $(wx)[i+1..n+k]...
- 11.2k
2
votes
Is $\{x2y : |x| = |y|, x\in A, y\in\{0,1\}^*, d(x,y) = k\}$ context-free for some infinite regular language $A$?
Let $F=\{x2y : |x| = |y|,\ x\in \{0\}^*,\ y\in\{0,1\}^*,\ d(x,y) = 1\}$, the language of all strings $0^n2y$ where $y$ consists of $n-1$ $0$s and one $1$.
Note that $F=\{0^p00^q20^q10^p: p\ge0, q\ge0\}...
- 34k
2
votes
Accepted
Formal language rewrite rules: strange notation
Yes, I think that's basically the intent. I guess the book is trying to write grammars without grammatical symbols. For me, it's abuse of notation, but that's pretty common.
Because there is no formal ...
- 11.2k
1
vote
What's grammar for a^n b^n c^n d^n
May I propose the following indexed grammar $G= ( \{S,A,C\}, \{a,b,c,d\}, \{f\}, S )$:
$S[\sigma] \to S[f\sigma]$
$S[\sigma] \to A[\sigma]\, C[\sigma]$
$A[f\sigma] \to a\, A[\sigma]\, b$, $\quad A[\...
- 27.6k
Only top scored, non community-wiki answers of a minimum length are eligible