Questions tagged [formal-grammars]
Questions about formal grammars, generative descriptions of formal languages.
1,251
questions
0
votes
1
answer
129
views
Stuck on Converting to Chomsky Normal Form,
I am supposed to be changing this to Chomsky Normal Form and then to Greibach form, but I am still having a few difficulties changing it to the first form.
Here is the language:
S → AA|SBBa|b
A → ...
CommunityBot
- 1
1
vote
1
answer
555
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 | ...
CommunityBot
- 1
1
vote
1
answer
38
views
Communication complexity of Dyck language
I've been reading papers on streaming algorithms and ran across the following question which I haven't been able to answer: Consider the Dyck language $Dyck(2)$ over the alphabet $A = \{(,),[,]\}$ and ...
D.W.♦
- 156k
1
vote
0
answers
15
views
Number of DCFG parse tree nodes with respect to input length
I read the question and answer at Number of nodes of a parse tree when the Grammar is in CNF?, and I'm curious about a related matter: obviously with a unrestrained LR grammar (as opposed to CNF) the ...
- 111
0
votes
2
answers
651
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 ...
- 28.3k
2
votes
2
answers
48
views
Derivation trees to show a given grammar is ambiguous
Given the grammar with productions:
\begin{align}
S \rightarrow aSb \mid SS \mid \lambda\\
\end{align}
I would like to show that it is ambiguous. As I understand it, if you can show that some string ...
- 1
1
vote
1
answer
370
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 "...
CommunityBot
- 1
0
votes
1
answer
118
views
Determining recursive enumerability of given languages
I came across following problem:
$L=\{M$ is a turing machine $M$ accepts two strings of different length $\}$
$L=\{M$ is a turing machine $M$ accepts atleast two strings of different length $\}...
CommunityBot
- 1
0
votes
0
answers
20
views
Lambda Calculus with State
I want to define a typed domain-specific lambda calculus which can simulate the sequence execution like common programming language. I wonder how to give its corresponding BNF, can I use ...
- 1
0
votes
1
answer
330
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 ...
CommunityBot
- 1
1
vote
4
answers
3k
views
Context sensitive grammar for $\{a^{2^n}\mid n\geq 0\}$
I want to build a context sensitive grammar for the language $\{a^{2^n}\mid n\geq 0\}$. I think it should be something like this
\begin{align*}
S &\to aA \mid a\\
aA&\to aaaA \mid aa
\end{...
1
vote
1
answer
37
views
Is the class of star-free languages just the complement to counter languages within the regular language class?
So I'm kind of confused as I'm not that deep into the algebraic theory of languages.
The wikipedia article states:
Another way to state Schützenberger's theorem is that star-free languages and ...
- 67
1
vote
1
answer
73
views
Not respecting the 3rd rule of a LL(1) grammar
I'm trying to build a grammar that violate only the 3rd rule. I'm trying to figure out what kind of grammar would not respect that.
I think the grammar has to be left-recursive to not respect it.
if ...
CommunityBot
- 1
0
votes
1
answer
734
views
How to determine valid handle for given bottom up parser?
I came across following question:
Consider the grammar:
$E → E + n\text{ | }E × n\text{ | }n$
For a sentence n + n × n, the handles in the right-sentential form of the reduction are
(...
CommunityBot
- 1
1
vote
0
answers
19
views
Parsing expression grammar for a language consisting of sentences with one character added or removed anywhere
Given a parsing expression grammar for a language, is there a way to make a parsing expression grammar for a new language that consists of the valid strings from the original language, plus the ...
- 111
4
votes
1
answer
341
views
Why is Dyck-2 so important for the Chomsky-Schützenberger theorem?
I have read a lot of times, that models that can parse Dyck-2 are of great importance. It appears that Dyck-2 is interchangeably used like Dyck-N.
Afaik the Chomsky-Schützenberger representation ...
- 29.8k
-1
votes
0
answers
77
views
Convert CFG to CNF
I have been struggling with this conversion problem. Would very much appreciate some verification on this.
Given:
S' -> S $ ($ is a terminal)
S -> a A B | b B A | ε
A -> a | S
B -> b ...
- 1
4
votes
1
answer
9k
views
Removing Left Recursion from Context-Free Grammars - Ordering of nonterminals
I have recently implemented the Paull's algorithm for removing left-recursion from context-free grammars:
Assign an ordering $A_1, \dots, A_n$ to the nonterminals of the grammar.
for $i := 1$ to $n$ ...
CommunityBot
- 1
1
vote
0
answers
51
views
Correct way to show example of ambiguous grammar
Facing confusion due to two different texts stating different ways to show examples of ambiguous grammar, though the example exists in the first book.
The second book gives a different example, as ...
- 750
0
votes
1
answer
33
views
An elementary question about grammar
Recently, I am studying grammar in automata. And, I have few information about this subject.
I have a grammar with rules $\{S\to ASA, A\to aA, A\to \epsilon\}$.
Is it true if I say that $S\to aASA$ ...
- 29.8k
0
votes
1
answer
55
views
Let P be the language of palindromes over the alphabet Σ = {0, 1}. and let P‘ be the subset of the palindromes with different numbers of 0s and 1s
Let P be the language of palindromes over the alphabet Σ = {0, 1}. and let P‘ be the subset of the palindromes with different numbers of 0s and 1s. Is P' context-free? I know that for the language of ...
- 29.8k
1
vote
0
answers
30
views
How need help to specify a grammar for arithmetic expressions
I am trying to come up with a grammar for arithmetic expressions with the following order of operations:
Parentheses
Factorials
Exponents
Functions / unary plus and minus
Juxtaposition (implied ...
- 111
0
votes
1
answer
166
views
How to demonstrate unambiguous CFG and CNF?
I have to show that if G is an unambiguous CFG, the transformed grammar G' in CNF is also unambiguous. But couldn't come up with something concrete. I could only visualize the case where the grammar G ...
CommunityBot
- 1
1
vote
1
answer
139
views
Dangling else determinism
The natural grammar for dangling "else" is ambiguous.
But there exists an unambiguous version of the grammar that links the "else" to last uncompleted "if" statement.
Is this version also ...
CommunityBot
- 1
0
votes
1
answer
81
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 &...
CommunityBot
- 1
0
votes
1
answer
50
views
How is $\{a^m b^n c^p d^q \mid m*n=p+q\}$ context sensitive?
I have been trying to understand how the language $L = \{a^m b^n c^p d^q \mid m*n=p+q\}$) is context-sensitive?
I first encountered this question here.
Would be grateful if you could provide some ...
CommunityBot
- 1
1
vote
1
answer
72
views
Is $L=\{1^n2^n3^m : n\neq m\}$ context free?
Is the language $L=\{1^n2^n3^m : n\neq m\}$ context free?
I checked and it satisfies the pumping lemma (Right?). Does it also satisfy Ogden's lemma, or any other test for being non-context free?
- 76
0
votes
1
answer
37
views
Find Grammar for L(G) ={a^i b^j c^k | k = i*j ;i, j ≥ 1}
Find a Grammar G, so that L(G) = {a^i b^j c^k | k = i*j ;i, j ≥ 1}
Hello, I have difficulties solving this. I had a similar exercise, where the k was i+j, which was easier, because the solution was to ...
CommunityBot
- 1
1
vote
1
answer
108
views
What complexity class is this set of grammars? In between NL and P?
Given a grammar where (every rule has the form $X \to YZ$, $XY \to Z$ or $X \to a$), (($X \to YZ$) implies ($X \to ZY$)) and (($XY \to Z$) implies ($YX \to Z$)) where $X,Y,Z$ range over nonterminals ...
CommunityBot
- 1
0
votes
2
answers
5k
views
Removing epsilon transition from context-free grammar
I have the following context-free grammar from which I have to remove epsilon transitions:
$S \to 0A0|0$
$A \to BC|2| CCC$
$B \to 1C | 3D | \epsilon$
$C \to AA3 | \epsilon$
$D \to AAB | 2$
By ...
CommunityBot
- 1
1
vote
1
answer
75
views
Language of equal numbers of as, bs, cs in any order not context-sensitive?
In his book "Foundations of Computing", professor Allison shows an example of "language of equal numbers of as, bs, and cs, but in any order", formally: $L = \{ w \in \{a,b,c\}^*\ |...
- 29.8k
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 ...
CommunityBot
- 1
0
votes
1
answer
37
views
The language of chains with twice as many $a$s as $b$s is regular?
I am trying to understand the pumping lemma and its instrumentation to show a certain language is not regular. My first attempt was the following problem:
Let $L$ be the language of all words that ...
CommunityBot
- 1
10
votes
1
answer
451
views
Shift-resolve parsing - questions
I've recently came across a paper describing the parsing technique
mentioned in the title. Unfortunately, the terminology used in said paper
is somewhat beyond my comprehension, so I've been ...
CommunityBot
- 1
2
votes
2
answers
135
views
Generating a recursive descent parser for grammar having Kleene star
From what I have been taught, I cannot use left-recursive, nondeterministic, or ambiguous grammars in recursive descent parsers. So, here is the grammar:
\begin{align}
&E \to E+T \mid T \\
&T \...
CommunityBot
- 1
-1
votes
1
answer
57
views
Is { a^nb^na^n} a context-sensitive language?
The language $L_1 = \{ a^nb^nc^n \}$ is often given as an example of a context-sensitive language.
I am wondering if the language $L_2 = \{ a^nb^na^n \}$ belongs also to the same category?
- 12.5k
0
votes
1
answer
44
views
Doubt in pumping lema for context-free language
I have a doubt related to pumping lemma in CFL for which I dont find an answer, so I think is very easy because no one wonder about. The lemma says:
My doubt is: Is there any restriction related to ...
- 5,359
1
vote
1
answer
367
views
Negative lookahead in LR parsing algorithm
Consider such a rule in grammar for an LR-family parsing generator (e.g YACC, BISON, etc.):
Nonterminal : [ lookahead not in {Terminal1, ..., TerminalN} ] Rule ;
...
CommunityBot
- 1
0
votes
1
answer
148
views
How do I represent this regular expression in regular grammar?
Question: Is the regular expression and regular grammar equivalent?
I've look on some examples of regular grammar however I don't think I fully understand how to convert regular expression to its ...
CommunityBot
- 1
3
votes
2
answers
610
views
2
votes
1
answer
7k
views
Converting CNF to GNF
I'm studying context free grammars and I can grasp how to create context free grammars given a set notation, and now to convert these context free grammars to Chomsky Normal form but I am utterly ...
1
vote
0
answers
31
views
What is a formal grammar equivalent to one-way stack automaton?
As the title says, is there a formal grammar characterization of the class of one-way stack languages?
- 11
0
votes
0
answers
34
views
Nonterminal Complexity of a context-free grammar
Suppose $G$ is a CFG.
$G = (N, T, P, S)$,
$Var(G)$ as the cardinality of $N$
$Var(L) $= min {$Var(G)$ | G is a context-free grammar and $L(G) = L$}.
I have a problem in understanding a part of proof ...
- 1
0
votes
0
answers
18
views
Decide if complement of context-free language is also a context-free language
Consider the following grammar $G$:
$$S \rightarrow SA \ | \ AS \ | \ aXb \ | \ bXa, \ \ \ X \rightarrow \# \ | \ BXB, \ \ \ A \rightarrow a \ | \ b \ | \ \#, \ \ \ B \rightarrow a \ | \ b$$
Decide if ...
- 13
3
votes
1
answer
2k
views
Is a machine Turing-complete when it can decide a context-sensitive language?
If a machine can decide a context-sensitive language (like the language of palindromes with a non-linear center) is that fact a proof that the machine is Turing-complete?
Can this be used to prove ...
D.W.♦
- 156k
0
votes
1
answer
79
views
Is this grammar LL(1) and what is it's parsing table?
Let G be a grammar with non-terminal A, terminal a and these productions:
A -> A a
It is ...
- 1,018
1
vote
1
answer
32
views
Equivalence of LR(k) and LL(k′) parsers
Are there languages that can be parsed by an LR(k) parser but not by an LL(k′) parser for any k′?
CommunityBot
- 1
0
votes
0
answers
50
views
Removing null production from cfg
While removing null production from cfg as below,
S->ABC
A->aA|^
B->bB|^
C->aaC|^
now as shown above we know that A,B and C all are ...
0
votes
0
answers
47
views
Right-regular grammar conversion to NFA: production rule with only one variable on right side
I'm trying to convert a right regular grammar to an NFA.
I understand that I need to create a state for every variable and add transitions according to the production rules.
But what if there is a ...
0
votes
0
answers
45
views
How to Remove Left Recursion from this Grammar?
How to remove left recursion in the following Grammar:
S→Bb/a
B→Bc/Sd/e
Im new to this, below is the way I'm doing it:
...
- 1