Questions tagged [formal-grammars]
Questions about formal grammars, generative descriptions of formal languages.
1,251
questions
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 ...
- 11
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
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 ...
- 21
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
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
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 ...
- 67
-1
votes
0
answers
78
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
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$ ...
- 13
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 ...
- 23
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
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
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 ...
- 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\}^*\ |...
- 155
-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?
- 155
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 ...
- 187
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 ...
- 181
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
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 ...
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 ...
- 155
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 ...
- 103
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 ...
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
0
votes
0
answers
37
views
Devising a grammar for language L = { a^xb^ya^xb^y | x, y >= 0 }
I've been trying to come up with a proper grammar for this sort of language:
L = { aˣbʸaˣbʸ | x, y >= 0 }
I have failed to find a way to enforce consistent generation of terminals on either part (...
- 1
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′?
- 11
3
votes
2
answers
2k
views
Mike Sipser and Wikipedia seem to disagree on Chomsky's normal form
Here's what Wiki says:
And here's what Mike Sipser says in his Introduction to Theory of Computation:
The problem arises when you try to read the two definitions - Mike Sipser seems to be suggesting ...
- 51
0
votes
0
answers
16
views
step 2 of CFG conversion to Chomsky's normal form
in the step where you have to remove the epsilons, would you need to remove something like this:
A -> Bε
Or would you simply remove the ones that have epsilon by itself like this:
A -> ε
-1
votes
1
answer
50
views
The book says 27 terminals but I only see 10. Where are they?
On page 103 of Mike Sisper's Introdution to Theory of Computation, it says that the grammar has 27 terminals (26 being the letters of the English Alphabet and 1 being the space character) but in the ...
- 51
1
vote
0
answers
42
views
How to develop intuition to come up with Context Free Grammar?
So i'm taking this class automata and complexity at georgia tech and we were given practice material for our exam.
one of the question is to give context free grammar for these two languages
and the ...
- 11
1
vote
1
answer
70
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
89
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
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 | ...
- 111
0
votes
0
answers
30
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
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 ...
2
votes
0
answers
136
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
57
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
53
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
24
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
21
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
47
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
74
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
55
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
49
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
41
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
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 &...
- 111
0
votes
1
answer
115
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 ...
