Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

Filter by
Sorted by
Tagged with
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 ...
shar's user avatar
  • 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), ...
thearchitector's user avatar
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 ...
targat's user avatar
  • 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 ...
Mohamad S.'s user avatar
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 ...
GR33NTE4's user avatar
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 ...
J. Linne's user avatar
  • 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 ...
NumberAddicted's user avatar
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 ...
zzzz's user avatar
  • 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: ...
David's user avatar
  • 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 ...
Mohamed Houssein Douici's user avatar
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 ...
philipp's user avatar
  • 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 ...
tomashauser's user avatar
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: ...
Oleg Dats's user avatar
  • 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: $(), ()(), (()...
Oleg Dats's user avatar
  • 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\,|\...
Ido's user avatar
  • 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, ...
Abhishek Ghosh's user avatar
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$. ...
Ramasamy Kandasamy's user avatar
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 ...
Jack Sparrow's user avatar
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 ...
Travis's user avatar
  • 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 ...
Charlie Parker's user avatar
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 $...
John's user avatar
  • 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 "...
hengxin's user avatar
  • 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)), .... ...
hengxin's user avatar
  • 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. ...
user145559's user avatar
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 ...
DannyNiu's user avatar
  • 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 ...
hengxin's user avatar
  • 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 ...
Swordow's user avatar
  • 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. ...
ladhee's user avatar
  • 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 ...
supcem's user avatar
  • 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 <...
stimulate's user avatar
  • 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 ...
phoenix's user avatar
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 &...
rdesai's user avatar
  • 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 ...
rdesai's user avatar
  • 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: ...
Kiruphasankaran Nataraj's user avatar
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 ...
Abhishek Ghosh's user avatar
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 ...
Node.JS's user avatar
  • 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 ...
Angelo Marcelino's user avatar
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 ...
Thomas Baruchel's user avatar
3 votes
2 answers
610 views

Dragon book exercise 4.4.5, why is aaaaaa not recognized by the recursive descent parser?

...
user avatar
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 ...
Peter Lenkefi's user avatar
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 ...
orlp's user avatar
  • 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}\}$...
Frank's user avatar
  • 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 ...
Finlay Weber's user avatar
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 ...
namasikanam's user avatar
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 ...
Gunther Schadow's user avatar
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 ...
Brijesh joshi's user avatar
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 ...
D. Petrov's user avatar
  • 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 $$ ...
zoldxk's user avatar
  • 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: ...
grammartest's user avatar
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 ...
D. Petrov's user avatar
  • 175

1 2
3
4 5
26