Questions tagged [formal-grammars]
Questions about formal grammars, generative descriptions of formal languages.
1,169
questions
3
votes
0
answers
31
views
Is there an alternative for the formal language theory that could be used for flowchart diagrams?
I am creating a tool for validating, parsing and interpreting flowchart diagrams on diagrams.net, and it is neccessary to give users an opportunity to define a set of rules for the diagram. So, in the ...
0
votes
0
answers
47
views
Defining grammar for $L=\{a^ib^ic^jd^j| i \ge j \ge 0\}$
I need to define a grammar for $L=\{a^ib^ic^jd^j| i \ge j \ge 0\}$ as I wasn't told about any restrictions for the grammar, e.g context-free or context-sensitive, I assume any derivation rules can be ...
- 241
0
votes
1
answer
31
views
When is a grammar ambiguous or When is a grammar not ambiguous?
I was looking at an example of grammar from the website: grammer example
which is as follows:
S → aB / bA
S → aS / bAA / a
B → bS / aBB / b
I believe they forgot to write: A -> a
Next, we are going ...
0
votes
1
answer
59
views
Decidability of a context free Grammar
Say that a Context Free Grammar is red when it accepts every word of length 3 that begins with a, and extremely red when it accepts every word that begins with a.
Is redness decidable? or Semi ...
- 1
1
vote
1
answer
51
views
Language generated by $S \to aAb|Sb$, $A \to aAb|ab$
Let $G = (\{A,S\}, \{a,b\}, S, P\}$ be the grammar with the following productions:
\begin{align}
& S \to aAb | Sb \\
& A \to aAb | ab
\end{align}
What is the language $L(G)$ generated by the ...
- 115
-1
votes
0
answers
31
views
Does my solution follow the FNC for a context-free grammar?
From the starting point we have this grammar:
S→AA|AB
A→aBa|BbB|BabB
B→abB|C
C→Cc|Ac
The first step is to remove empty (ε) and unitary values.
From the example ...
3
votes
1
answer
72
views
What is the formalism used to describe optional arguments called?
Most command line tools have an usage described by using square brackets for optional parts and just writing out required parts (like in regexes) for example:
foo [opt1[opt2...]] req1 req2 [opt3...]
...
-3
votes
1
answer
43
views
What's grammar for a^n b^n c^n d^n
What wiil be grammar rules for the language L={a^n b^n c^n d^n; n>0}
- 1
2
votes
0
answers
22
views
Finding a Context Free Grammar for Different No. of a and b AND Different No. of b and c [duplicate]
The question is from my homework: Is the language $\{a^ib^jc^k\mid i,j,k\geq0\land i\neq j \land j \neq p\}$ a context-free language (CFL)? If yes, please provide a context-free grammar for it. I ...
0
votes
1
answer
32
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
0
votes
0
answers
19
views
Can you recommend some materials on Turing Machine?
I need exercises with answers to practice building Turing machines. Books, online resources etc.
Can anyone recommend something?
- 1
1
vote
1
answer
30
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
58
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
39
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 ...
- 313
-1
votes
1
answer
79
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 ...
- 13
0
votes
0
answers
37
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
0
answers
51
views
Why is the LR(1) automaton deterministic?
Let $G = (V, \Sigma, P, S)$ be an LR(1) grammar. We can define a non deterministic $\lambda$-automaton[1] as follows. First of all we extend the grammar with an additional symbol $S'$ which will be ...
- 101
0
votes
1
answer
69
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
45
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
2
votes
2
answers
115
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:
...
- 23
0
votes
1
answer
41
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
0
answers
29
views
How to prove a number of LR(0) states?
I have this grammar $G_n, n\ge 2$:
$$\begin{align}S&\to A_iB_i, 1\le i \le n\\
A_i&\to a_jA_i\mid a_j, 1\le i\land j\le n\land j\ne i\\
\end{align}
$$
How can I prove that this grammar has ...
- 137
0
votes
1
answer
21
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 ...
- 121
0
votes
0
answers
29
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:
...
- 287
0
votes
1
answer
79
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: $(), ()(), (()...
- 287
0
votes
1
answer
16
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
91
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,034
0
votes
0
answers
37
views
Complexities of algorithm for generating strings of length k from CNF grammar
Question: For the code "generate_language_rec" below, explain whether the time and space complexities are Linear, Polynomial or Exponential ( find a tight upper-bound ) in $k $. Assume the ...
- 211
0
votes
1
answer
67
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
251
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
18
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
26
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 ...
- 2,910
0
votes
4
answers
106
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 $...
- 1
0
votes
0
answers
41
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,179
2
votes
1
answer
49
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,179
0
votes
1
answer
34
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
32
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 ...
- 151
2
votes
1
answer
40
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,179
2
votes
1
answer
52
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
39
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. ...
- 39
1
vote
1
answer
36
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
0
answers
20
views
Tips on making a grammar LL(1)?
So I currently am given the following grammar, and I have to make it LL(1).
To do this, I need to remove ambiguities, eliminate left recursion, and left factor if necessary.
But looking at this, it's ...
0
votes
1
answer
22
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
29
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
51
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
27
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
0
votes
0
answers
76
views
How to convert PDA to CFG and make a state diagram
I'm trying to understand this but I can't figure out how to proceed, I have an initial procedure but I don't know if it's right, could someone give me examples of how to do this?
My attempt
S→q0 Z q2
→...
1
vote
1
answer
101
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
132
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,034