Questions tagged [formal-grammars]
Questions about formal grammars, generative descriptions of formal languages.
1,197
questions
1
vote
1
answer
30
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, ...
- 139
0
votes
1
answer
13
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 ...
- 139
0
votes
0
answers
14
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:
...
- 139
4
votes
1
answer
85
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 ...
- 141
0
votes
0
answers
14
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
56
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
26
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
29
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
268
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 ...
- 171
0
votes
0
answers
19
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:
...
- 395
0
votes
1
answer
38
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-...
- 395
2
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 ...
- 395
1
vote
1
answer
43
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$, ...
- 111
0
votes
0
answers
33
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 ...
- 345
2
votes
1
answer
120
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
137
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, ...
- 241
0
votes
0
answers
26
views
LR parsing and soft keywords
A lot of modern program languages these days allow for keywords to be used for variable names, function names and class names. They call these keywords soft-keywords. Only if the soft-keyword is used ...
- 217
1
vote
1
answer
50
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, ...
- 279
1
vote
1
answer
41
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\...
- 279
1
vote
2
answers
54
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\...
- 279
0
votes
1
answer
55
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 ...
- 279
0
votes
3
answers
136
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, ...
- 41
-2
votes
1
answer
47
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
51
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
54
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.
- 217
2
votes
0
answers
68
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
90
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
79
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 ...
- 155
0
votes
1
answer
87
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 ...
- 155
0
votes
0
answers
38
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 ...
- 155
1
vote
1
answer
72
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 ...
- 155
3
votes
0
answers
32
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
55
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
36
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
75
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
54
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
77
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
52
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
40
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
35
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
64
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
44
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 ...
- 454
-1
votes
1
answer
82
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
43
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
55
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
122
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
57
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
133
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