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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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}\#...
user avatar
  • 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{(}\;\...
user avatar
  • 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 ...
user avatar
  • 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$ ...
user avatar
  • 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(...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 \...
user avatar
  • 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 ...
user avatar
  • 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.
user avatar
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.: ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 27.6k
2 votes

Making a simplest possible CFG to recognize the language L = {a^i b^j c^k | i + j ≥ 2k}

Grammar ...
user avatar
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. ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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. ...
user avatar
  • 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 ...
user avatar
  • 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$
user avatar
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 ...
user avatar
  • 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]...
user avatar
  • 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\}...
user avatar
  • 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 ...
user avatar
  • 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[\...
user avatar
  • 27.6k

Only top scored, non community-wiki answers of a minimum length are eligible