Questions tagged [formal-grammars]
Questions about formal grammars, generative descriptions of formal languages.
1,251
questions
1
vote
1
answer
257
views
How to remove ambiguity from the grammar?
I want to remove ambiguity from the grammar below:
S → ABC
A → abA | ab
B → b | BC
C → c | cC
I have removed left recursion and left factoring and obtained the grammar as follows:
S → ABC
A → abA'
A' →...
0
votes
1
answer
62
views
Why the Following Grammars Are Not in CNF
I am reading the book "Automata, Formal Languages, and Automata" written by Dr. Emre Sermutlu and in page 153, it is stated that the following grammars are not in Chomsky Normal Definition (...
- 143
1
vote
0
answers
127
views
How does ANTLR4 handle optional rules?
Are the following two stat rules equivalant?
stat : 'if' expr 'then' stat ('else' stat)? ;
...
- 9,501
0
votes
0
answers
18
views
The maximal choice smallest grammar algorithm. Is this an exact algorithm or an approximation?
When we speak of a variable, sometimes we will mean the string it expands to, and other times, the variable itself. Let $t \leqslant s$ mean substring.
Take the string $s = a^6$. Then its ...
- 495
0
votes
0
answers
33
views
An ingenious exact smallest grammar algorithm for strings over a single letter, $s \in \{a\}^*$. First enumerate the start rules up to commutation
Take $s = a^{10}$ for our example string. Compute the set of all potential grammar reducing variable-rules:
$$
A \to aa \\
B \to aaa \\
C \to aaaa \\
D \to aaaaa
$$
There is always exactly $\left\...
- 495
0
votes
1
answer
38
views
What context-free grammar recognizes a list of numbers 1 - N in order?
I'm looking for a context-free grammar that recognizes precisely the numbers 1 - N in order:
...
- 401
0
votes
0
answers
62
views
Grammar for prime length strings
How do we write an unrestricted grammar for
$$L = \{a^n \ | \ n \ \text{is prime}\}$$
I know that $L$ is neither regular, nor context-free.
Also, I know how to build a Turing Machine for $L$. The idea ...
- 140
0
votes
2
answers
95
views
Context free grammar for $L= \{0^i1^ic0^j1^j | j = i+1 \}$
Description
This is an exercise for Formal Language course, I'm asked to find a grammar for language:
$L = \{ 0^i1^ic0^j1^j | j = i+1 \}$
As an example: 01c0011 can be generated using this language, ...
- 3
0
votes
1
answer
206
views
Find the language generated by the Context Free Grammar
I am trying to find the language generated by this context-free grammar
S → aSb | bbY | Yaa
Y → bY | aY | ε
I understand that one way to solve is this to find set ...
- 111
1
vote
0
answers
55
views
minimum number of non-terminals so that for all context-sensitive languages there is a non-contracting grammar
Every context-sensitive language $\subseteq \Sigma^* = \{a,b\}^*$ can be expressed using an essentially non-contracting grammar.
With just one non-terminal symbol, we can't express all context-...
- 181
0
votes
0
answers
51
views
context free grammar for ${\{0^i1^j0^k1^l0^m \mid i, j, k, l, m \ge 0, i \le k\text{ or }j = m\text{ (or both)}\}}$
I'm trying to come up with a context free grammar for the following language: $${\{0^i1^j0^k1^l0^m | i, j, k, l, m \ge 0, i \le k \text{ or } j = m \text{ (or both)}\}}$$
I'm able to come up with ...
0
votes
1
answer
1k
views
BNF and EBNF Syntax for while loops in C#
Given the programming language C#, how would I be able to write the BNF and EBNF grammar syntax of its while loop?
After trying to search and understand more, I got this as my BNF grammar for while ...
0
votes
1
answer
30
views
Grammar where tokens can be transmuted
I have a grammar which is mostly LL(1), save for the fact that some tokens may be promoted to larger integer types.
For example, let take the following grammar
<...
- 101
1
vote
1
answer
69
views
Minimal-length strings which are substrings of no string in a given CFL
Is there an algorithm for enumerating a sequence of minimal-length substrings composed of terminal symbols within some CFG which are not substrings of any string in the language defined by that CFG? ...
- 33
0
votes
1
answer
88
views
Greibach Normal Form: Proof every sentential form is of the form xy with x terminals and y variables
For any grammar in Greibach normal form, every sentential form obtained from S by a partial left-most derivation is of the form xy with x terminals and y variables.
I think that this can be proven ...
- 89
2
votes
1
answer
119
views
What role does an asterisk serve in Backus–Naur Normal Form?
Suppose that you were reading some production rules for a context-free grammar in Backus–Naur Normal Form
What does the asterisk (*) mean?
In the example below, ...
0
votes
1
answer
90
views
How can we escape the pipe character in Backus–Naur Normal Form?
Suppose that you were writing down the syntax rules for something like C++ as a context-free grammar in Backus–Naur Normal Form
How can you distinguish between the pipe character as symbol in C++ or ...
4
votes
1
answer
128
views
Formal grammar of MIU system
The MIU system, famous from Douglas Hofstadter, is a semi-thue system with the following rules:
Xi → Xiu
mX → mXX
XiiiY → XuY
XuuY → XY
and a start axiom "mi"
I have tried to find a formal ...
- 143
0
votes
0
answers
26
views
Canonicalizing Arbitrary EBNF Expressions
From what I understand, LL and LR parsing require a grammar to be in "canonical form", i.e. only productions of the form A -> b1 b2 ... bn, where ...
1
vote
1
answer
323
views
determining whether a context-free language is regular
I was wondering how to determine (with proof) whether the context-free language generated by the following context-free grammar $G$ is regular, where $S$ is the start variable and $a$, $b$ are the non-...
- 289
1
vote
1
answer
40
views
if $RA$ is context-free, is $A$ context-free?
If $RA$ is context-free for a regular language R, is $A$ context-free?
I think this statement is true. Let G be the CFG given by the rules $S_0\mapsto LA_1, S\mapsto LA_1, A_1\mapsto SA_2 | RS | 1, ...
- 289
0
votes
1
answer
54
views
prove that the unique language $A$ such that $AB$ is context free for all languages B is the empty set
Prove that the unique language $A\subseteq \Sigma^*$ such that $AB$ is context free for all languages $\subseteq \Sigma^*$ is the empty set.
If $A$ is not the empty set, there should be a way to ...
- 289
4
votes
1
answer
302
views
What are the languages produced by context free-grammars with backspace?
If we add backspace to the output alphabet, are all the languages produced still context-free? (If not, then what are they?)
The word (a, b, c, Backspace, Backspace), for example, gets interpreted as ...
- 181
0
votes
1
answer
49
views
Proving grammar equivalence in simple grammar (generate any sequence of three characters)
Goal is proving grammar equivalence
Upper-case symbols are non-terminal.
Lower-case symbols are terminal.
The start symbol is S.
A grammar production rule is non-...
- 401
3
votes
2
answers
1k
views
Is it always possible to order grammar rules so that all the symbols on the left will be contained on the right in a previous rule?
This is about unrestricted grammars
Assume S is the start symbol. Assume 1 and 0 are ...
- 401
1
vote
1
answer
421
views
Prove a subset of a regular language is regular, context-free but not regular or not context free
I've been tasked with solving this problem, but I'm not sure where to begin:
Let $L$ be a context-free language. $L'$ contains all the words that belong to $L$ which can't be defined as $z=uvwxy$, ...
- 113
2
votes
1
answer
159
views
Formal language rewrite rules: strange notation
I'm reading "Program=Proof" by Samuel Mimram, and they use a notation for defining a formal language that I'm not familiar with.
Here is how "Program=Proof" defines a formal ...
- 184
1
vote
3
answers
413
views
How to prove the language of words $a^ib^jc^k$ where $\min(i,j)\le k\le\max(i,j)$ is not context-free?
I want to prove that $\mathcal M =\{a^ib^jc^k \mid \min(i,j)\le k\le\max(i,j)\}$ is not a CFL.
Using the pumping lemma, let $p$ be the constant, then I choose $w=a^pb^pc^p$.
When I separate to cases, ...
- 239
1
vote
1
answer
70
views
is there a non-context free language A such that A1 is context free?
Is there a non-context free language A over the alphabet $\{0,1\}$ such that $A1 := \{a1 : a\in A\}$ is context free?
I was thinking of the language $A = \{0^n 1^{n-1} : n > 0\}.$ Unfortunately, ...
- 289
1
vote
1
answer
71
views
Is $\{x2y : |x| = |y|, x\in A, y\in\{0,1\}^*, d(x,y) = k\}$ context-free for some infinite regular language $A$?
For two equal-length binary strings $x$ and $y$, let $d(x,y)$ denote the Hamming distance. Prove or disprove: there exists a positive integer $k$ such that the language $\{x2y : |x| = |y|, x\in A, y\...
- 289
1
vote
2
answers
66
views
Show that the Hamming distance of $wx$ and $xw$ cannot be 1
Let $w$ and $x$ be two binary strings. Show that the Hamming distance of $wx$ and $xw$ cannot be 1.
I think one approach is a proof by contradiction. I was thinking of explicitly writing out $w = w_1\...
- 289
0
votes
1
answer
92
views
Prove or disprove that $\{xc o(x) :x \in A\}$ is context-free, where A is a regular language
Suppose o is a map on strings to strings. For every language R, we let $o(R) := \{o(x) : x \in R\}$. If o(R) is a regular language for every regular language R, then prove or disprove that the ...
- 289
0
votes
3
answers
398
views
Find a Context-Free Grammar for $L = \{a^wb^xc^yd^z | w + x = y + z\}$
I have to find a CFG for the given expression:
$L = \{a^wb^xc^yd^z | w + x = y + z\}$
This is what I've tried so far:
S -> aSd | B | ϵ
B -> bBc | ϵ
It works for expressions like: aabcdd, ...
-2
votes
1
answer
75
views
expression/pattern for language where product of number of 0s and 1s is even
I am trying to solve one of the sample test problems in which I have to write an expression/pattern for the following language:
$\{w \in \{0, 1, 2\}^*: {\#}_{0}(w) ∗ {\#}_{1}(w) \text{ is even}\}$
I ...
- 31
0
votes
1
answer
112
views
find LR(1) items of the first state
I need to calculate the LR(1) items of the following grammar:
S -> E
E -> E + T
E -> T
T -> ID
T -> ( E )
I can not even calculate the first group {[...
- 3
0
votes
2
answers
470
views
LR(1) grammar that can not be transformed an LL(1) grammar
Looking for an example of a LR(1) grammar that can not be turned into an LL(1) grammar that parsers the same language.
- 237
2
votes
0
answers
76
views
Is the language $L = \{{a^{2n+1}b^{m+2}a^n | m \neq 2n}\}$ context-free?
$L = \{{a^{2n+1}b^{m+2}a^n | m \neq 2n}\}$
I tried to split $L$ in 2: when $m > 2n$ and $m<2n$, however both resulting languages are not context-free, so I did not find out anything about $L$.
...
-3
votes
1
answer
266
views
Prove a stronger version of the pumping lemma for context-free languages
Let $L$ be a context-free language. Prove that there exists integer $p>0$ such that
$ \forall z\in L $ such that $ |z|\ge p $, there exists a partition $ z=uvwxy $ such that
$|vwx|\le p$
$|vx|\...
- 121
0
votes
2
answers
245
views
Design a CFG for $L=\{ w \in \{ 0,1 \}^* \}$, where $w$ contains at least three ones
$L=\{ w \in \{ 0,1 \} \}$ where $w$ contains at least three ones
Here is one solution for the productions:
$S \to A1A1A1A$
$A \to 1A | 0A | \epsilon$
However, now I have a question. Could I modify the ...
- 167
0
votes
1
answer
146
views
Context-free grammar for language $L = \{u \in \{a, b\}^* \mid |u|_a = |u|_b\}$ [duplicate]
I need to find the production rules for the following language:
$L = \{u \in \{a, b\}^* \mid |u|_a = |u|_b\}$
Well, the first thing I could come up with is
$S \to aSb | \epsilon$
But this only covers ...
- 167
0
votes
0
answers
94
views
Union of two context-free grammars and their productions
Is it possible to create an union of two context-free grammars? I found a PDF material from the university of Iowa where they claim that it's possible but I just don't know how. They had that for ...
- 167
1
vote
1
answer
535
views
Context-free grammar for $L=\{ a^nb^m | n \le m+3 \}$
I'm having problems determining the productions for a CFG describing the language $L=\{ a^nb^m | n \le m+3 \}$
where $n,m \ge 0$
I'm very new to this so this example might be a little harder, but ...
- 167
3
votes
1
answer
62
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 necessary to give users an opportunity to define a set of rules for the diagram. So, in the ...
0
votes
0
answers
139
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 ...
- 261
0
votes
1
answer
927
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 ...
- 305
0
votes
1
answer
116
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
60
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 ...
- 121
3
votes
1
answer
89
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
564
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
25
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 ...
