Questions tagged [formal-grammars]
Questions about formal grammars, generative descriptions of formal languages.
1,251
questions
0
votes
1
answer
189
views
Finding a context free grammar (CFG) for a non-context free language (CFL) a^n b^n c^n
It is known that the language $\{a^nb^nc^n|n\geq0\}$ is not context-free (we can prove it using the pumping lemma, as shown here: Is $a^n b^n c^n$ context-free?). Yet, this answer claims it has found ...
- 1
1
vote
1
answer
58
views
Constructing an unrestricted grammar for XWX, where W is the reverse of X
I'm trying to construct an unrestricted grammar for strings of the form XWX, where W is the reverse of X, over the alphabet {a, b}.
I think I can apply similar logic to the a^nb^nc^n solution (below), ...
2
votes
1
answer
346
views
How to identify Context-Sensitive Grammar?
Context-Sensitive Grammar is defined as a 4 tuple G = (V, Σ, R, S) where:
V is a finite set of elements known as variables.
Σ is a finite set of elements known as terminals
V ∩ Σ = Null (empty set)
S ...
- 25
1
vote
1
answer
292
views
Prove/Refute that $L=\{w\$x^R \ |\ x\ is\ a\ substring\ of\ w\}$ is a regular language
I was solving some exercises about CFL from past years' homework and faced this question.
Question: Given the language $L=\{w \# x^R \ | \ x\ is\ a\ substring\ of\ w\}$, prove/refute if it's regular ...
- 453
0
votes
1
answer
112
views
Context Sensitive Grammar for $x \# x^R \# x$
This language is given.
$L = \{\; x \# x^R \# x \mid x\in \{a,b\}^*\;\}$
I have to figure out a context sensitive grammar for it.
I've tried several rules already but it's hard to make a copy of the ...
- 23
0
votes
0
answers
67
views
Languages with number of $a$'s a perfect square
Is there any finite automata ((N/D)FA, NPDA, DPDA, or any variation of a Turring Machine) that can accept the following language:
$\{s \text { is a string over } \{a,b\} \text { such that the number ...
- 141
0
votes
1
answer
330
views
How to find context sensitive grammar for words like ww?
I'm studying formal languages and automata, and on the section of learning how to find productions that generates the grammar, I've done some exercises pretty well and was able to do some of the ...
0
votes
1
answer
75
views
How would my parsing functions look for this grammar?
Suppose we have the grammar
$$S \to aA | BA $$
$$A \to a | bB | \epsilon $$
$$ B \to cB | d$$
I know that I need to write four different functions in order to parse this grammar.
They are
...
- 3
3
votes
2
answers
325
views
LALR(1) grammar for simple math parser
I am trying to write a simple parser for a small calculator project, that should be able to parse e.g. the following inputs:
...
- 33
0
votes
1
answer
82
views
Decidability of a given grammar if it is regular
According to my course the question "Is $L(G)$ regular?" undecidable. But I was more interested in knowing the exact algorithm or proof that makes this question undecidable. To further ...
3
votes
0
answers
30
views
Is there a context-agnostic concept of automatic (log-)text parsing that supports human reader filtering out redundancy?
This question is about ideas I regularly think about, and I would like to know what concepts already exist. Also I am not sure at all if this really makes sense, by now it is just a crazy idea
...
- 131
0
votes
1
answer
49
views
How to prove correctness of a bidirectional converter between two CF grammars?
I have a converter between two context-free grammars which are both describing the same language but one uses infixes other than prefixes, has different symbols and sometimes switches order of ...
- 129
0
votes
0
answers
140
views
How to count the number of nodes for a tree generated by context free grammar derivation?
Given context free grammar I use breadth first search and left most derivation rule to generate all possible words for a given language.
For example:
...
- 299
0
votes
1
answer
422
views
Disambiguating grammar for Dyck language
Given the following simple grammar for a language that contains all strings with matched parentheses:
\begin{align}
&s \to ss \\
&s \to (s) \\
&s \to ()
\end{align}
Examples: $(), ()(), (()...
- 299
0
votes
1
answer
19
views
Computing Earley Parsing Steps
I am trying to understand Earley parsing algorithm using an example. The grammar I use produces all the palindromes over $\Sigma=\{a,b,c\}$:
\begin{align*}
Z & \to S\\
S & \to a\,|\,b\,|\,c\,|\...
- 163
0
votes
1
answer
637
views
Remove left recursion from a grammar without necessarily removing epsilon production
Consider the grammar
$$S →Aa∣b$$
$$A →Ac∣Sd∣ϵ$$
Construct an equivalent grammar with no left recursion and with minimum number of production rules.
$\tag {GATE-CS-1998}$
While solving this question, ...
- 1,112
0
votes
1
answer
446
views
Reduce-reduce conflict in SLR vs LALR
I was wondering if I could say any of the following is true.
Given a grammar $G$,
If the LALR parser has reduce-reduce conflict for $G$, then the SLR parser also has reduce-reduce conflict for $G$.
...
0
votes
1
answer
672
views
Context free grammar for $1^n 0^m 1^k 0^p$ where $n+k=m+p$
i need to convert this CFL to CFG
$$ L = \{\; 1^n 0^m 1^k 0^p \mid n\ge 2, k,m,p\ge 1, n+k=m+p\;\} $$
I am trying to solve this problem for a few days but i couldn't. Is there anyone to help me? I'm ...
- 11
0
votes
0
answers
40
views
Find CFG for bin(n)bin(2n+3)^R
Where bin(n) is the shortest binary representation of n.
First, we can see that we can rewrite it as $bin(n)bin(2(n+1)+1)^R$ which implies that the second word will always start from 1.
We can also ...
- 1
1
vote
0
answers
65
views
How does one parse a string into an AST (Abstract Syntax Tree) directly instead of to a CST (Concrete Syntax Tree)?
I wanted to parse strings to AST data structures instead of CSTs - which introduce a lot of intermediate nodes like terminal that might not be needed. I am not sure if one first creates a CST and then ...
- 3,000
2
votes
4
answers
296
views
Making a simplest possible CFG to recognize the language L = {a^i b^j c^k | i + j ≥ 2k}
The language given is $L = \{a^i b^j c^k\mid i+j \ge 2k\}$ for which I need to construct a simplest possible Context Free Grammar.
I tried understanding but I could only go as far as making sense of $...
- 21
1
vote
1
answer
370
views
How to prove that this "priority" strategy (in ANTLR4) solves the "dangling-else" ambiguity?
As shown in this post @ stackoverflow, ANTLR4 seems able to resolve the "dangling-else" ambiguity @ wiki in the following "if-then-else" grammar by prioritizing the "...
- 9,501
2
votes
1
answer
381
views
How does LALR(1) parser behave compared to LR(1) paser?
In Section 4.7.4 of the book "Compilers: Principles, Techniques, and Tools" (2nd Edition), it reads:
"The revised parser (LALR(1)) behaves essentially like the original (LR(1)), .... ...
- 9,501
0
votes
1
answer
36
views
References to deterministic time complexity of language classes
It's fairly well known that $REG \in TIME(n)$. I would like to know similar inclusions for the language classes $DCFL$ and $CFL$.
I have found a variety of claims for these classes on the internet. ...
0
votes
1
answer
35
views
Grammar where the precedence of condition operators are asymmetric with regard to assignment operators
In Unix shell programming, there's the ideom:
program1 && program2 && program3
where successful completion of ...
- 192
2
votes
1
answer
58
views
What does $g \to \lambda$ mean in the L-System for the dragon curve?
I am playing with L-System using the wonderful tool jflap. Below is the L-System for the dragon curve in the "JFLAP book: JFLAP – An Interactive Formal ...
- 9,501
2
votes
1
answer
141
views
Convert a dfa to rule for a asterisk case
Here is a simple but very common grammar rule case in EBNF format, the Statements is a none terminal symbol and Statement is ...
- 19
-1
votes
1
answer
48
views
I can't visualize what happens when we pump v and y in pumping lemma for $a^n b^n c^n$
If you need some context-: https://www.andrew.cmu.edu/user/ko/pdfs/lecture-11.pdf around page 7.
Case 1-: Say vxy contains ab
So when I pump v and y, what will get pumped? And how the result would be. ...
- 37
1
vote
1
answer
294
views
CFG for L={a^i b^j c^i; i,j > 0}
I worked a bit on this and got this-:
S->ABC
A->aA/a
B->bB/b
C->cC/c
The obvious problem here is I am unable to count number of a's and c's which ...
- 47
0
votes
1
answer
29
views
What is the subset of CFGs called where each expansion must be the same?
I was wondering about a kind of grammar where we can expand rules of the form A -> X|Y|... with A being a nonterminal and <...
- 103
0
votes
1
answer
41
views
LALR lookahead is wrong, why?
I am studying LALR(1) parser and I have this question:
Consider the following Grammar
S - > V = E
E - > F | E+F
F - > V | int | (E)
V - > id
Construct the LALR(1) parsing table for this ...
- 3
1
vote
2
answers
83
views
PDA with multiple element access - $i$ - access PDA
We define an $i$ - access PDA as a PDA that can manipulate the top $i$ characters in the stack, where $i>0$.
Given a transition function of the form $\delta(p,x,c,d) \to (q,c')$, where $d \le i, d &...
- 15
0
votes
1
answer
52
views
Variant of Chomsky Normal Form for Languages with Strings of Length $\ge 2$
Given a context-free grammar $G$ for a language $L$, where $L$
contains strings of length greater than 2, show that there exists some
context-free grammar $G'$ which generates $L$ such that every rule ...
- 15
1
vote
1
answer
232
views
Stuck with shift-reduce conflicts on yacc on grammar to generate palindromic strings on {0,1}
I have written a yacc program for generating palindromic strings consisting of 0s and 1s. Here is the rules section of the yacc program below:
...
1
vote
1
answer
321
views
Hierarchy of parser grammars vs Chomsky hierarchy of grammars and the comparsion of the language acceptance power of each parser grammar
While reading the text Modern Compiler Implementation in C by Andrew Appel I came across the hierarchy of grammar given below.
The above diagram is very helpful in understanding the correlation among ...
- 1,112
0
votes
1
answer
70
views
Formal proof of existence of equivalent parse tree for each derivation
Where I can find formal proof of there exists an equivalent parse tree for each derivation? There is a lot of informal proof of equivalency on the internet but I need formal proof to reference it in a ...
- 101
0
votes
1
answer
1k
views
Can a grammar that has only one leftmost derivation tree for every sentence, have more than one rightmost derivation tree for some sentence?
I'm currently studying the book Engineering a Compiler by Keith Cooper, and in chapter 3, there is the following definition:
A grammar G is ambiguous if some sentence in L(G) has more than one ...
1
vote
1
answer
151
views
Easy-to-prove example of non-contextual language
When studying Chomsky's hierarchy of languages (starting from type 3), I find enlightening to encounter some language that can't belong to the current type but which very obviously belong to the next ...
- 131
3
votes
2
answers
610
views
1
vote
0
answers
46
views
Algorithm for transforming all left-recursive rules in a grammar into direct left-recursive
I'm probably missing a lot of terminology here, so I'll try to rather be too clear than too vague.
I have a Context-Free grammar as an input, that might contain direct or indirect left-recursion ...
- 208
3
votes
1
answer
184
views
Is the emptiness problem for PEGs decidable?
The emptiness problem for Context Free Grammars is decidable. Does the same hold for Parsing Expression Grammars (PEGs)? That is, is it decidable given a PEG $G$ to find whether $L(G) = \emptyset$ or ...
- 12.7k
3
votes
1
answer
946
views
Context free grammar for strings with more $a$'s than $b$'s
I would like to prove that the grammar $G$ with the rules
$$
S \to SS \mid aSb \mid bSa \mid a \mid \varepsilon
$$
generates the language $L = \{w \mid \text{$w$ has at least as many $a$'s as $b$'s}\}$...
- 323
0
votes
2
answers
137
views
How to define a formal language for describing procedural activities
I do not have a formal computer science background here so I am looking for pointers.
How would you advice I go about describing a formal way to describe procedures like cooking recipes, manufacturing ...
- 145
1
vote
1
answer
174
views
What is the formal definition of precedence and associativity in programming language?
The concept of precedence and associativity seems straightforward.
The operator precedence is a collection of rules that reflect conventions about which procedures to perform first in order to ...
- 205
1
vote
0
answers
33
views
Has anyone seen the following string classifier discussed?
The closes related question I have found for this is Find string patterns preferably in regex for string streams, but it has no answer and is also a little less constrained as my idea.
Given a set of ...
- 111
2
votes
1
answer
2k
views
Left recursive grammar to right recursive grammar
I am studying conversion from left recursive grammar to right recursive grammar. The given grammar is
$$E \to E + T \mid T $$
It's equivalent right recursive grammar will be
$$\begin{align}E &\to ...
- 195
1
vote
1
answer
83
views
Proof of an interesting language being non-context free
Let $\Sigma = \{a, b, c\}$ and $L = \{wa^{1 + k + 2n}b^nw^{rev}\mid n, k \in \mathbb{N}_0, w \in \Sigma^*\}$. It is clear that $L$ is context free, but the question is the following:
Let $L'$ be the ...
- 175
0
votes
1
answer
409
views
What's the Context-Free grammar of this language : $L= \{a^n b^m c^p d^q |m+n=p+q, n,m,p,q \geq0 \}$ [duplicate]
I was trying to find the context-free grammar of
`$L= \{a^n b^m c^p d^q |m+n=p+q, n,m,p,q \geq0 \}$ but I'm stuck.
This is what I did so far:
$$ S \to X S Y | \lambda$$
$$X \to a|b$$
$$Y \to c|d
$$
...
- 111
-3
votes
1
answer
269
views
How can I convert from DFA in to regular grammar?
I have following information.
0 1
-> *q0 q0 q1
q1 q1 q2
q2 q2 q0
I have to convert this in to a regular grammar.
I wrote this:
...
- 11
1
vote
2
answers
63
views
If $p(n) := \sum_{i=0}^ka_in^i$ where $a_i\in\mathbb{N}, a_k \ne 0$ AND $k \ge 2$, is $L = \{0^n1^{p(n)} \mid n\in\mathbb{N}\}$ context-free?
I have the really strong feeling it is indeed NOT context-free, since the language $1^{n^k}$ for $k\ge 2$ is not context free (proven by the pumping lemma) and, in a sense, "the order of ...
- 175