Questions tagged [formal-grammars]
Questions about formal grammars, generative descriptions of formal languages.
155
questions
28
votes
2
answers
46k
views
How to prove that a language is context-free?
There are many techniques to prove that a language is not context-free, but how do I prove that a language is context-free?
What techniques are there to prove this? Obviously, one way is to exhibit ...
D.W.♦
- 156k
25
votes
1
answer
9k
views
How to show that L = L(G)?
Specifying formal languages by giving formal grammars is a frequent task: we need grammars not only to describe languages, but also to parse them, or even do proper science. In all cases, it is ...
- 72k
76
votes
1
answer
15k
views
Language theoretic comparison of LL and LR grammars
People often say that LR(k) parsers are more powerful than LL(k) parsers. These statements are vague most of the time; in particular, should we compare the classes for a fixed $k$ or the union over ...
- 72k
32
votes
4
answers
31k
views
How to prove that a grammar is unambiguous?
My problem is how can I prove that a grammar is unambiguous?
I have the following grammar:
$$S
→ statement
∣ \mbox{if } expression \mbox{ then } S
∣ \mbox{if } expression \mbox{ then } S \mbox{ else } ...
- 521
8
votes
3
answers
4k
views
Context-free grammar for $L = \{a^{2^k}, k \in\mathbb{N}\}$
In an exercise, I am asked to find a context free grammar for language $L = \{a^{2^k}, k \in \mathbb{N}\}$.
I have been trying to use a "doubling" variable. If $a^{2n} \in L, n\in\mathbb{N}$ then use ...
- 215
6
votes
2
answers
9k
views
Converting to CFG from a CFL? [duplicate]
I am trying to learn CFG. Now to make a CFG from a CFL it is really difficult for me.
Is there any simple rule or steps so that I can easily find a CFG for a CFL. I am trying to solve one problem ...
- 173
9
votes
3
answers
1k
views
Context-sensitive grammar for the language of words concatenated with themselves
I'm looking for a context-sensitive grammar that describes the following language:
$L = \{ ww \mid w ∈ \{a,b\}^{\ast}, |w| ≥ 1\}$ .
I've got problems with the fact that no rules such as $X \to \...
- 91
8
votes
2
answers
25k
views
Context Free Grammar for {a^ib^j | i,j ≥ 0; i ≠ 2j}
Can someone help with this:
$L=\{a^ib^j \mid i,j \ge 0 \text{ and } i \ne 2j\}$
I'm trying to write a grammar for this language?
I don't know how to do this.
I tried this:
$S \rightarrow aaAb \...
- 115
5
votes
2
answers
47k
views
How to convert PDA to CFG
I learned how to convert context-free grammar to pushdown automata but how can I do the opposite? to convert PDA to CFG?
For example: to write CFG for the automata
My attempt:
$S=A_{03}$ because $...
- 449
20
votes
1
answer
35k
views
Intersection of context free with regular languages
The intersection of a context free language L with a regular language M, is said to be always context free. I understood the cross product construction proof, but I still don't get why it is context ...
- 399
7
votes
3
answers
21k
views
Regular Expression to Context-Free Grammar
Anyone knows if there is an algorithm for directly write the context-free grammar that generates a given regular expression?
- 173
40
votes
2
answers
6k
views
Are there inherently ambiguous and deterministic context-free languages?
Let us call a context-free language deterministic if and only if it can be accepted by a deterministic push-down automaton, and nondeterministic otherwise.
Let us call a context-free language ...
- 12.8k
16
votes
2
answers
5k
views
Are regular expressions $LR(k)$?
If I have a Type 3 Grammar, it can be represented on a pushdown automaton (without doing any operation on the stack) so I can represent regular expressions by using context free languages. But can I ...
- 355
3
votes
1
answer
2k
views
Context Free Grammar for language L
Can someone help with this:
$L=\{a^ib^j \mid i,j \ge 1 \text{ and } i \ne j \text{ and } i<2j\}$
I'm trying to write a grammar for this language?
I tried this:
$S \to S_1 \mid S_2 \\
S_1 \to aXb ...
- 115
1
vote
1
answer
111
views
Is it possible for a Turing machine to be able to reduce a grammar and tell where it fits in chomsky hierarchy?
For example:
This looks like a context free grammar:
𝑆 → 𝑄𝑅𝑇
𝑄 → 𝑎𝑄 | 𝑎
𝑅 → 𝑏𝑅 | 𝑏
𝑇 → 𝑐𝑇 | c
but it can be reduced to this regular language:
𝑆 → 𝑎𝑆 | 𝑎𝑅
𝑅 → 𝑏𝑅 | 𝑏𝑇
𝑇 → 𝑐𝑇...
- 13
25
votes
2
answers
29k
views
Is the complement of { ww | ... } context-free?
Define the language $L$ as $L = \{a, b\}^* - \{ww\mid w \in \{a, b\}^*\}$. In other words, $L$ contains the words that cannot be expressed as some word repeated twice. Is $L$ context-free or not?
I'...
- 741
19
votes
2
answers
5k
views
How can I convert the Turing machine the recognizes language $L$ into an unrestricted grammar?
According to this Wikipedia article, unrestricted grammars are equivalent to Turing machines. The article notes that I can convert any Turing machine into an unrestricted grammar, but it only shows ...
- 375
11
votes
3
answers
2k
views
Decidable languages and unrestricted grammars?
Turing machines and unrestricted grammars are two different formalisms that define the RE languages. Some RE languages are decidable, but not all are.
We can define the decidable languages with ...
- 9,037
10
votes
5
answers
2k
views
Is there a known method for constructing a grammar given a finite set of finite strings?
From my reading it seems that most grammars are concerned with generating an infinite number of strings. What if you worked the other way around?
If given n strings of m length, it should be possible ...
- 260
5
votes
2
answers
3k
views
Unrestricted grammar to generate $a^{n^2}$
I have been asked to find a grammar that will generate the language $\{a^{n^2}:n \ge0\}$ in an exercise. So far I tried to replicate the previously written characters with my grammar rules but it didn'...
- 97
4
votes
2
answers
336
views
Context free grammar construction
My problem with CFG is, I am to generally create ones that don't have requirements such as:
$\qquad \{a^m b^n \mid m \le n \le 2m \}$
I have no clue where to begin, and how to approach it. I was ...
CSTHEORY
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{...
- 65
1
vote
1
answer
57
views
What complexity class is this set of grammars?
Given a grammar where every rule has the form $X \to YZ$, $XY \to Z$ or $X \to a$ where $X,Y,Z$ range over nonterminals and $a$ ranges over terminals, and given a nonterminal $S$ and a terminal $a$, ...
- 401
0
votes
1
answer
100
views
What complexity class does is this set of grammars? NL-complete?
The unrestricted grammars characterize the recursively enumerable languages. This is the same as saying that for every unrestricted grammar G there exists some ...
- 401
19
votes
1
answer
2k
views
Is language equality for linear context-free grammars decidable?
Let's consider two context-free grammars $G_1$ and $G_2$ and ask the following question: Is $L(G_1) = L(G_2)$, that is, are the two grammars equivalent?
In general, this problem is undecidable. ...
user51117
17
votes
3
answers
3k
views
Decidable non-context-sensitive languages
It is arguable that most languages created to describe everyday problems are context-sensitives. In the other hand, it is possible and not hard to find some languages that are not recursive or even ...
13
votes
2
answers
6k
views
Is there any way to distinguish between LL(k) and LR(k) grammar?
I am recently studying about Compilers designing. I came to know about two types of grammar one is LL grammar and other is LR grammar.
We also know the facts that every LL grammar is LR that is LL ...
- 359
11
votes
2
answers
6k
views
How can I prove this language is not context-free?
I have the following language
$\qquad \{0^i 1^j 2^k \mid 0 \leq i \leq j \leq k\}$
I am trying to determine which Chomsky language class it fits into. I can see how it could be made using a context-...
- 435
7
votes
4
answers
542
views
Why does $A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$ generate a context free language for regular $L$?
How can I prove that the language that the operator $A$ defines for regular language $L$ is a context free language.
$A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$, where $x^R$ is the ...
- 1,697
5
votes
2
answers
8k
views
unambiguous grammar that produce equal number of a and b
is there any unambiguous grammar on alphabet={a,b} that can produce strings which have equal number of a and b (e.g. "aabb" , "baba" , "abba") ?
- 71
5
votes
1
answer
657
views
Inducing a context free grammar [closed]
I have a file containing a subset of possible strings from a context free language. I am looking for a mechanism to induce the grammar from this information. Is that possible?
- 153
2
votes
1
answer
1k
views
Is this unambiguous grammar equivalent?
I have a simple context free grammar $(\{A\}, \{(,)\}, R, A)$, which consists of this one production rule:
$A \rightarrow AA\, \vert\, (A)\, \vert\, \epsilon$
I believe this is ambiguous! For ...
- 123
2
votes
1
answer
3k
views
Finding a unambiguous grammar
As an exercise we were supposed to find a grammar $G$ that generates language $L(G) = \{w \in \{a,b\}^* \mid |w|_a = |w|_b\}$.
That was not so hard, I found a grammar which I think is correct:
$S \...
- 77
2
votes
2
answers
18k
views
How to construct Context Free Grammar of words with equal number of 0's and 1's [duplicate]
i am trying to find a cfg for this cfl
L = $\{ w \mid w \text{ has an equal number of 0's and 1's} \}$
is there a way to count the number of 0's or 1's in the string?
- 41
1
vote
2
answers
780
views
Is the language of words that contain a square regular or context-free? [duplicate]
$ L = \{w \in\{a,b\}^{*} : \exists_{x,y,z} , w=xyyz \wedge y \neq \epsilon \}$
I have a problem with this exercise. I need to determine if this language is regular, context-free or not both and ...
- 53
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 ...
- 401
0
votes
1
answer
347
views
Example Context free grammar
Is there a nice way to give context free grammar for
$$\{a^nb^ma^kb^l:n+m=k+l\}?$$
From PDA point of view it seems we just push + on stack if we see a, push + on stack if we see b, pop + from stack ...
user39969
0
votes
1
answer
30
views
What complexity class is this set of grammars? RE?
Given a grammar where every rule has the form $X \to YZ$, $XY \to Z$, $X \to a$, or $X \to \epsilon$ where $X,Y,Z$ range over nonterminals and $a$ ranges over terminals, and given a nonterminal $S$ ...
- 401
37
votes
2
answers
5k
views
What does "context" in "context-free grammar" refer to?
There are lots of definitions online about what a Context-Free Grammar is, but nothing I find is satisfying my primary trouble:
What context is it free of?
To investigate, I Googled "context ...
- 2,957
22
votes
4
answers
2k
views
Are there other ways to describe formal languages other than grammars?
I'm looking for mathematical theories that deal with describing formal languages (set of strings) in general and not just grammar hierarchies.
- 323
19
votes
2
answers
2k
views
Can there be 'dead states' in a context-free grammar?
Can a context-free grammar include "dead states" from an automaton, such as
$$G = \big(\{a, b, c\}, \{A, B, C\}, \{A\to aB, B\to b, B\to C, C\to cC\}, A\big)\,?$$
The production rules $B\to C$ and $...
- 293
16
votes
3
answers
2k
views
What would you get if you add parameters to context free grammars?
I was thinking of grammars for indendation-sensitive languages and it looks like CF grammars would do the trick if combined with parameters. As an example, consider this fragment for simplified Python ...
- 285
15
votes
2
answers
1k
views
Are the Before and After sets for context-free grammars always context-free?
Let $G$ be a context-free grammar. A string of terminals and nonterminals of $G$ is said to be a sentential form of $G$ if you can obtain it by applying productions of $G$ zero or more times to the ...
- 9,036
15
votes
5
answers
6k
views
How is non-ambuiguity different from determinism?
I am trying to understand what is meant by "deterministic" in expressions such as "deterministic context-free grammar". (There are more deterministic "things" in this field). I would appreciate an ...
- 1,378
12
votes
2
answers
11k
views
Finding the language generated by a context-free grammar
This is a question from the Dragon book (I apologize for translation mistakes, I don´t have the English version on hand):
What language is generated by this grammar?
$S \rightarrow a S b S \mid b S a ...
- 223
9
votes
1
answer
27k
views
Convert CFG to PDA
Is there any set of rules or methods to convert any context free grammar to a push down automata?
I already found some slides online but I wasn't able to understand them.
In slide 10 he speaks ...
- 227
9
votes
1
answer
20k
views
Left recursion and left factoring -- which one goes first?
if I have a grammar having a production that contains both left recursion and left factoring like
$\qquad \displaystyle F \to FBa \mid cDS \mid c$
which one has priority, left recursion or left ...
- 355
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
7
votes
3
answers
3k
views
How to generate a context sensitive grammar for www
I am trying to solve for my exam coming up and have no clue how to generate the grammar for Context sensitive languages
for example how do i proceed on this kind of question.
Give a context-...
- 145
6
votes
1
answer
1k
views
Can every linear grammar be converted to Greibach form?
Can every linear grammar be converted to a linear Greibach normal form, a form in which all productions look like $A \rightarrow ax$ where $a \in T$ and $x \in V \cup \{\lambda\}$?
($T$ is the set of ...
- 2,193