Questions tagged [formal-grammars]
Questions about formal grammars, generative descriptions of formal languages.
1,251
questions
0
votes
0
answers
28
views
I am trying to design an LL(1) Parser that accepts T = {a, b *, +, ?, E, U, (, ) }
I am trying to design an LL(1) Parser that accepts regular notation where 'E' represents epsilon, and 'U' represents "or" like ' | '.
So far I made one that accepts T = { a, b, *, +, (, ), E}...
-2
votes
1
answer
92
views
Removing left recursion with terminals only
I have a grammar:
$G → id > id$
$| id < id$
$| G and id$
Does anybody know how I can do left recursive elimination on this one, when it doesn't have any extra non terminals?
- 109
1
vote
0
answers
25
views
Compile XPath Abbreviated Query to Unabbreviated version
The Xpath 3.1 presented by W3C includes the full grammar of the language with both abbreviated and unabbreviated syntax.
I am interested in references (if any) for any formal work done to compile/...
- 11
3
votes
2
answers
218
views
Context free grammar for $L = \{w \text{ | }w \in \{a,b\}^*, |w|_a=|w|_b-1\}$
I'm trying to find a grammar for $L = \{w \text{ | }w \in \{a,b\}^*, |w|_a=|w|_b-1\}$, which is proving to be tricky.
I know that $L_2 = \{w \text{ | }w \in \{a,b\}^*, |w|_a=|w|_b\}$ has the following ...
- 239
0
votes
1
answer
425
views
Computing FOLLOW sets of left recursive grammar
Left recursive ambiguous expression Grammar:
$E \rightarrow E+E \mid E*E \mid (E) \mid \mathbf i\mathbf d$
I tried computing FIRST and FOLLOW sets of both left recursive grammar and after ...
- 147
1
vote
1
answer
50
views
Is there a formal language of Combinatory Logic's expressions?
The Combinatory Logic uses expressions of the form (x y) called "applications" (here, we have an "application of x to y"). Thus, the language of CL is a set of "parenthetic ...
- 111
1
vote
1
answer
132
views
Derivation from grammar
Given the grammar $G=(\{S, L_x, R_x, W_x\}, \{a,b\}, P, S)$ derive the words $abaaba$ and $aabbaabb$.
$$
P=\left\{
\begin{align}S\phantom{{}_x R_y} &\to \epsilon \mid L_x R_x,\\
L_x \...
- 13
1
vote
1
answer
52
views
Finding a grammar for $L=\{a^nb^mc^rd^s| n+m<r+s\}$
I am trying to find a grammar for $L=\{a^nb^mc^rd^s| n+m<r+s\}$, which has the hint of it having "some similarity" to $L=\{a^ib^j|i<j\}$
This last one is quite easy to get ($S\to aSb | ...
- 239
2
votes
4
answers
175
views
If $L$ is regular then $L^{|2|}=\{w_1w_2 \mid w_1,w_2\in L, |w_1|=|w_2|\}$ is context-free
I have found a problem about proving whether $L^{|2|}=\{w_1w_2 \mid w_1,w_2\in L, |w_1|=|w_2|\}$ is context-free or not, knowing that $L$ is regular
So far I know that:
There are examples where $L$ ...
- 239
1
vote
2
answers
154
views
Finding a grammar for $L = \{ 0^x1^y0^z1^w | x+w=y+z\}$
I have found an exercise where it tasks to provide a grammar and a pushdown automata for
$L = \{ 0^x1^y0^z1^w | x+w=y+z\}$
While finding a pushdown automata for it is quite easy (four states and two ...
- 239
1
vote
2
answers
258
views
Trying to remove ϵ rules from a formal grammar resulted in L(G) ≠ L(G')
I am trying to remove ϵ rules from the following grammar (after applying the remove redundant symbols algorithm): $G = (\{S,A,B,C\},\{0,1\},P,S)$, where the productions are
\begin{align}
&S \to AB ...
- 113
3
votes
1
answer
2k
views
Is there a method to generate the complement of a context-free grammar?
Given the languages $L_0 = {w \in \{0,1\}^*}$ such that $w$ is a palindrome and $L_1 = {w \in \{0,1\}^*}$ such that $w$ is not a palindrome, meaning $L_1$ is the complement of $L_0$, we want to find ...
- 1,111
0
votes
1
answer
36
views
Is the complement of the language generated by $S \to aSbS|\epsilon$ context-free?
How is it possible to prove whether the language $\{a, b\}^{∗} \setminus \{S → ε, S → aSbS\}$ is context free?
- 1
4
votes
1
answer
755
views
Context-free grammar for all words not of the form w#w
I was asked to define a CFG for the complement of $\{w\#w \mid w \in \{0,1\}^*\}$ and I'm struggling to define it. I think it is quite similar to defining a CFG for the complement of $\{ww \mid w \in \...
- 43
1
vote
1
answer
61
views
Trying to find two CFGs for the following languages
I'm trying to get CFGs for these two languages which still remain unsolved in my practice problems sheet:
$L = \{ a^kb^ra^m | m=k+r\}$
$L = \{ a^nb^m | 1\leq n\leq 2m\}$
With the first one, I thought ...
- 239
0
votes
1
answer
40
views
How can Chomsky hierarchy be applied to languages with alternated letters?
I have the following grammar, which I know it is regular because it can be represented by a finite state automata:
\begin{array}{l}
\mathrm{S} \rightarrow \mathrm{X} \mid \mathrm{Y} \\
\mathrm{X} \...
- 103
2
votes
1
answer
2k
views
What does it mean for a grammar to be LR(0)?
I am unsure what it means for a grammar to be $X$. More specifically, what it means for a grammar to be LR(0).
For part of an assignment I had to form the DFA for a grammar, which I had no issues with....
- 146
2
votes
1
answer
106
views
How can I show that this language is context sensitive?
I have this language $L=\{a^nb^nc^n,n\geq0\}$, I know this language is not context free, but I don't know how to show that it is context sensitive, do I have to use a PDA?
- 37
0
votes
1
answer
83
views
Formal proof of language accepted by a specific CFG
Let $G=(V,\Sigma,R,S)$ be the grammar given by the following rules:
\begin{align}
&S \to aS \mid B \\
&B \to abBc \mid \epsilon
\end{align}
Please provide a formal proof for the following ...
- 11
1
vote
1
answer
149
views
How do you create a sentential form in a given grammar?
I am given the following grammar:
$$S ::= aBS| abT |a$$ $$T::= d | dT$$$$B ::= da | ϵ | S$$
I need to decide whether $aBaabda$ can be produced in the given grammar.
I am unsure how the grammar can ...
- 146
1
vote
1
answer
957
views
How can we generate a grammar for $\{a^n b^n c^n d^n; n > 0\}$ if it is NOT context free?
This page on Wiki states that $\{a^nb^nc^nd^n \ | \ n > 0\}$ can not be generated by a CFG. This does not make sense to me as $\{$S $\to$ ABCD, A $\to$ aA | a, B $\to$ bB | b, C $\to$ cC | c, D $\...
- 194
0
votes
1
answer
101
views
Are these production rules for a formal grammar?
I have a question on if production rules of a formal grammar are being specified correctly. Wikipedia defines the syntax of grammars as the following finite set of production rules, where it states ...
- 175
-1
votes
1
answer
108
views
Transform grammar to Chomsky Normal Form
Question:
S → abSab | baSba | TT
T → aTa| bTb | ε
My answer:
Eliminate ε rules:
S-> abSab | baSba | TT | T
T-> aTa | bTb | aa | bb
Correct answer:
S → abSab | baSba | TT | abab | baba | T
T → ...
- 1
1
vote
2
answers
1k
views
How to tell if a grammar is LALR(1) formally?
There is an “informal” definition of $\operatorname{LR}(k)$ (can be recognised by a parser that looks at $k$ symbols ahead) and a “formal” one (as a property of the set of rightmost derivations ...
- 245
0
votes
2
answers
365
views
How do Context Sensitive Grammar systems work?
The Quest: Use context sensitive grammar (CSG) to produce an equal N number of repeating a, b, and c using the alphabet {a, b, c}. For example, if N = 5 use CSG and a, b, and c to produce a result ...
- 103
2
votes
1
answer
142
views
Linear Grammar in less than cubic time
I have a linear grammar $G$ and a string $s$. $G$ is is not limited to right or left linear only but rather has a mix of rules of both types.
Is there an algorithm to determine whether $s \in L(G)$ ...
- 33
2
votes
1
answer
64
views
Is “A -> aAA” convertible to regular grammar?
I have a simple grammar as below and wonder if it is convertible to regular grammar?
If yes, what is the conversion sequence? If no, how can we prove it?
...
- 123
1
vote
1
answer
231
views
How to find the language of a CFG from Production rules
I'm having problems in finding language of the CFG from given production rules. For example if the production rules are
\begin{align}
&S \to AS \mid \epsilon \\
&A \to aa \mid ab \mid ba \mid ...
- 25
7
votes
1
answer
466
views
What are the closure properties of LL(k) languages?
Suppose I have two LL languages $L_1, L_2$, both describable by LL($k$) grammars for the same $k$, and regular language $R$. Which of the following are also LL languages, and can they be described by ...
- 813
0
votes
1
answer
187
views
How should I understand left/right derivations of grammars and parse trees?
I'm having a hard time understanding how left/right derivations work. I have a very simple example that I've attempted but I don't really know how to check if it's correct.
$S \to NP$ $V$ $NP$
$NP \to$...
- 101
0
votes
0
answers
259
views
Converting a regular expression to a grammar and regular grammar
I am working on a pretty small lab for my university course and I'm having trouble converting a given regex into a set of regular definitions, then into a grammar and finally a regular grammar. I have ...
- 101
4
votes
1
answer
690
views
Is every unambiguous grammar regular?
While searching for an answer to this question I found out that there is an unambiguous grammar for every regular language.
But is there a regular language for every unambiguous grammar? How can I ...
- 151
0
votes
0
answers
92
views
a^ib^jc^k, i < j < k is a context-sensitive language, how can prove it as a context sensitive
I've been pondering this question for a long time, that $a^ib^jc^k, i < j < k$ is a context-sensitive language, how we can prove it to be context sensitive or
which grammar can generate such a ...
- 1
0
votes
0
answers
46
views
Do the SLR and LALR parsers of a same CF grammar have the same shift actions?
In theory, given that:
The LALR parser can be constructed by merging LR(1) states with the same core;
If $I$ is a LR(1) set of items, then $\text{core}(\text{GOTO}(I))=\text{GOTO}(\text{core}(I))$;
...
- 183
0
votes
0
answers
415
views
ANTLR G4 grammer for math expression
I am new to grammar and have written grammar for parsing math expression for asciiMath using ANTLR as below.
...
- 1
0
votes
0
answers
41
views
Constant single match regex
I am looking for the name (definition?) of X in:
A regular expression is X iff it has exactly one possible match.
Examples: <empty regex>, abc, ...
- 101
1
vote
0
answers
52
views
How to write "∀x.F(x)" for "F(x)=λx.Φ(x)" in one expression (sequel from question about "∀(λφ. (φ x m→ φ y))"?
This question is sequel from How to understand quantifier without predication " ∀(λφ. (φ x m→ φ y))"? which further explains the notation and context.
So - I have anonymous Boolean-valued ...
- 1,381
0
votes
0
answers
53
views
Is this grammar in Backus–Naur form?
I'm a newbie and a paper I'm reading specifies the following grammar:
...
- 1
0
votes
1
answer
1k
views
Converting PDA to CFG
I am trying to understand this example of converting PDA to CFG but I am not getting the idea quite right. I do have the general understanding of theorem that if $p,q\ \epsilon\ Q $ and $X \varepsilon\...
1
vote
0
answers
119
views
Is every language described by a grammar?
I read the following argument showing that not every language is described by a grammar:
For a fixed alphabet $\Sigma$ and variables $V$ there are uncountable many languages over $\Sigma$ since the ...
0
votes
1
answer
34
views
If a grammar G is left and right regular, why $||L(G)|| \leq ||P||$?
I was studying automata theory and formal languages and came across this question:
If a grammar $G$ is left and right regular, why $||L(G)|| \leq ||P||$ ?
I've searched the theory but I am missing ...
0
votes
1
answer
66
views
Is there any official terminology about something like double quotes "" grammar?
In many programming language string is a token.
For example:
...
- 275
0
votes
1
answer
268
views
Removing left factoring from Context-Free Grammar
I know that, removing left factoring is a simple task.
And i understand following procedure:
$S→aA | aB$
Becomes:
$S→aS'$
$S'→A|B$
Yet I'm running into problems with this particular grammar:
$S→AD|...
- 45
1
vote
1
answer
218
views
Enumerator for Word and Halting Problem
in theoretical computer science I learned for every recursive enumerable language there would be an enumerator and a grammar. So since word problem and halting problem are recursively enumerable, I ...
0
votes
1
answer
58
views
Is there a way to map the concatenation operation over strings to the addition operation over $\mathbb{N}$
Given an alphabet, say $\Sigma = \{0,1\}$, I can make a one-to-one mapping from all possible strings $x \in \Sigma^*$ to $\mathbb{N}$. This could be done by ordering $\Sigma^*$ lexicographically and ...
- 461
0
votes
1
answer
256
views
How to design a formal grammar to convert EBNF description to a list of CFG production rules
I would like to write a grammar to convert EBNF description to a list of CFG production rules, instead of an algorithm.
Can CFG production rules is generated from an EBNF description by a rewrite ...
1
vote
1
answer
53
views
Help with context free grammar excercise
So, I have an exercise in which I have to write a context free grammar for this language:
$$L = \{x \in L(a^∗b^∗c^∗) : |x|_a > |x|_c; |x|_b > 0; |x|_c ≥ 0\}$$
meaning every string with any ...
- 11
0
votes
0
answers
33
views
Is there any good method to find if a grammar is optimal for a problem?
I've been thinking about grammatical evolution problems and how the grammar influences the algorithm performance. It came to my mind the huge impact that the grammar that you're using has in the time ...
- 221
0
votes
2
answers
161
views
removing indirect left recursion
I want to remove indirect left recursion from these rules:
S-->TU,
T-->US|b,
U-->ST|a
I don't know if I can implement the algorithm correctly. ...
- 3
3
votes
0
answers
87
views
Are there context free grammars for all restricted Dyck paths?
A Dyck path is a finite list of $1$'s and $-1$'s whose partial sums are nonnegative and whose total sum is $0$. For example, [1, 1, -1, -1] is a Dyck path. Rather ...
- 131