Questions tagged [formal-grammars]
Questions about formal grammars, generative descriptions of formal languages.
1,226
questions
1
vote
1
answer
20
views
What is a contracting grammar (in opposition to a non-contracting grammar)?
In the Chomsky hierarchy what is corresponding to a contracting grammar?
I can find references to non-contracting grammars (which can be transformed into context-sensitive grammars accordingly to what ...
- 221
1
vote
1
answer
27
views
How would this grammar be converted to a non-left recursive rule?
With recursive-descent parsing, direct/indirect left recursive rules do not allow top-down parsing.
How would this grammar be converted to be non-left recursive?
...
- 11
1
vote
1
answer
78
views
CFG for the language {w ∈ {0, 1}∗ : w is a palindrome and |w| is divisible by 3}
The question is the following:
Construct CFG for the L = {w ∈ {0, 1}∗ : w is a palindrome and |w| is divisible by 3}.
I am able to construct CFG for the set of all palindromes as below:
S --> aSa | ...
0
votes
0
answers
17
views
First Set for this grammar? Is it Indirect Left-recursive
Given the grammar (Uppercase alphabet is non-terminal, lower-case alphabet is terminal), how to find FIRST set?
A -> mB | CD
B -> CBn | epsilon
C -> pA | epsilon
D -> q
This is NOT a ...
- 1
0
votes
1
answer
84
views
Is the language $L = \{0^i 1^j | i \ne 2j\}$ context free?
I have been trying to find a a CFG for this language generated.
I came to the conclusion that I need three parts
When $i \le j$
When $j < 2j < i$
When $j < i < 2j$
I was able to come up ...
2
votes
0
answers
130
views
Determining when a substring has a unique parse forest
Given an arbitrary (potentially ambiguous) context free grammar $G: \mathbb{G}$, and string $\alpha: \Sigma^\ast$, is there a decision procedure that returns whether appending and/or prepending ...
- 33
0
votes
0
answers
40
views
Methods of eliminating ambiguity in CFG
I am looking for all possible ways to find and eliminate ambiguity in CF grammar. Please share your knowledge or opinion (preferably you will indicate the literature so that I can familiarize myself)....
- 1
0
votes
0
answers
37
views
What should be the order of eliminating empty rules and unit rules when converting context free grammar to chomsky normal form?
Let's say that we have a context free grammar G, which is not in chomsky normal form, and we need to convert it to chomsky normal form.
The steps involved in the conversion are as follows:
Add a new ...
- 305
0
votes
1
answer
19
views
Do Left regular grammar describe a language containing the reverse of the strings described by the right regular grammar for another language?
Let's say that we have a regular language $L_1$ that is described by a right regular grammar. Now, assume we have a left regular grammar, can we describe the same language $L_1$ or would the left ...
- 305
0
votes
0
answers
19
views
Write grammar that produces a^2^i, for i>0 [duplicate]
How to write grammar for that language:
$$
a^{2^i}, i>0
$$.
Anyone could help?
0
votes
1
answer
26
views
In Context free languages, is it okay to substitute multiple same variables at the same time?
Let's say we have the following context free grammar:
$S \rightarrow a \\ S \rightarrow SS$
And we do the following two "derivations" for the same string:
aaa: $S \rightarrow SS \rightarrow ...
- 305
1
vote
1
answer
32
views
How can dfa have more than one sink state? Isn’t it the same state?
I can’t understand How can dfa have more than one sink state? Isn’t it the same state? Maybe there is some examples
- 11
1
vote
0
answers
45
views
What is the formal definition of a combinational logic?
Question Background
A finite-state machine can be defined as a 5-tuple as follows (Sipser, pg. 35):
The image below (taken from the Wikipedia article on combinational logic) seems to suggest that ...
- 111
0
votes
1
answer
36
views
Convert regex for comma separated value to CFG grammar
I have the following regex that I'm trying to convert to a CFG: e|a(,a)* (e representing the empty state). Basically I want to ...
2
votes
1
answer
22
views
Duplicate rules in CFG
Suppose I have the following CFG that I would like to bring to CNF
S -> TA | bA | Ab | b
A -> Aa|a
T -> Ab
Then I have two options to get rid of the ...
- 155
0
votes
1
answer
50
views
Simple description of the LR(0) table generator algorithm?
I have just implemented a parser on the relational database. Parsing is done with recursive query. Note: one commenter was misled by the word "recursive" before "query" to think &...
- 111
0
votes
1
answer
43
views
Why Regular Grammar is Left/Right Linear?
From the definition I know that regular grammar should be Left/Right Linear (ie it should have variable on Left/Right side of each production rules)
But, my question is why it is mandatory?
Can't we ...
1
vote
1
answer
88
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
48
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
44
views
How does ANTLR4 handle optional rules?
Are the following two stat rules equivalant?
stat : 'if' expr 'then' stat ('else' stat)? ;
...
- 9,379
0
votes
0
answers
29
views
How to prove the unambiguous of the grammar?
My question is the method to prove the grammar that is unambiguous. There may be no general method to prove it, but I want to know the the proof techniques.
For example, $E\rightarrow +EE\ |\ *EE\ |\ -...
- 1
0
votes
0
answers
16
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 ...
0
votes
0
answers
28
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\...
0
votes
1
answer
24
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:
...
- 411
0
votes
0
answers
57
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 ...
- 141
0
votes
2
answers
66
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
62
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
43
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
47
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
384
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
49
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
0
answers
30
views
Find a context free grammar for $0^n10^m1$, where n is even and m is odd
Let $$L_1 = \{0^n10^m1 | n, m \in N \text{ where n is even and m is odd} \}$$
I tried to build a cfg but I am not sure if it right or if it is the simplest solution.
$$ G_1: V = {S}, T = \{0, 1\}$$ ...
- 211
0
votes
1
answer
54
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
70
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, ...
- 151
0
votes
1
answer
56
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 ...
- 151
0
votes
0
answers
42
views
What is an example of some production rules which would allow parentheses, curly braces, and square-brackets to be interchangeable?
In computer programming, there are many different ways to write a for-loop.
Some examples are shown below:
...
- 151
4
votes
1
answer
112
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
16
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
164
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-...
- 279
1
vote
1
answer
32
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, ...
- 279
0
votes
1
answer
38
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 ...
- 279
4
votes
1
answer
290
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
0
answers
24
views
Given an instance of a HORN-SAT problem with at most 3 literals per clause, what context-free grammar is equivalent to deciding the problem?
Given an instance of a HORN-SAT problem with at most 3 literals per clause, what context-free grammar is equivalent to deciding the problem?
For example, here are some HORN clauses:
...
- 411
0
votes
1
answer
42
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-...
- 411
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 ...
- 411
1
vote
1
answer
207
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
0
votes
0
answers
70
views
Can the leaf nodes of a parse tree be labeled by a variable, a terminal, and the empty symbol; or only a terminal and the empty symbol?
When you are deriving a string using a context-free grammar (CFG), you
start with the start symbol and at the right side you have combinations of
variables (non-terminals) and terminal symbols.
Let's ...
- 355
2
votes
1
answer
147
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
254
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