Linked Questions
76 questions linked to/from How to show that L = L(G)?
5
votes
2
answers
8k
views
Defining a context-free grammar for $\{w \in \{0, 1\}^* : \#_0(w) = \#_1(w)\}$ [duplicate]
I have a language where each string in the language has even amount of $0$'s as $1$'s (e.g., $0101$, $1010$, $1100$, $0011$, $10$ are all in the language). I was hoping to define a context-free ...
- 181
0
votes
2
answers
3k
views
Proving that a CFG generates a language [duplicate]
Is a suitable way to prove that any given CFG generates (or not) any given language to draw its total language tree?
What if the tree is infinite? What would then be a better way to prove that a ...
- 264
-1
votes
1
answer
2k
views
Proving correctness of a CFG by induction on length of strings generated [duplicate]
Consider the following grammar with starting symbol of $S$.
$$S \rightarrow 0S11\;|\;S1\;|\;0$$
Let $L = \{0^i1^j:\; \ge 1\; and\; j \ge2i-2\}$ . Give a formal proof of the following claim : For all ...
- 49
0
votes
1
answer
839
views
How do I use induction to show that the language of a grammar is contained in a given set? [duplicate]
Given that I have the grammar
$\qquad\displaystyle G_1 = (\{a, b, c, d\}, \{S, X, Y \}, S, \{S → XY, X → aXb, X → ab, Y → cYd, Y → cd\})$,
how am I supposed to prove that
$\qquad\displaystyle S(G1) ...
- 11
4
votes
2
answers
177
views
Gyorgy E. ReveszExercise 1.1: Show the grammar $G$ generates the language $L$ [duplicate]
The exercise says
"Show that the grammar $G = \langle\{S\}, \{a, b\}, S, \{S \to \lambda, S \to aSb\}\rangle$
generates the language $L = \{a^i b^i \mid i = 0, 1, 2, \ldots\}$."
Now, I'm new to ...
- 213
1
vote
0
answers
527
views
Proof of completeness for CFG having twice as many zeroes as ones [duplicate]
One possible CFG containing twice as many zeros as ones can be,
S -> 0S0S1S | 0S1S0S | 1S0S0S | ϵ
(This CFG is redundant but it will do the job. So I am not interested in the redundancy. Other ...
- 136
2
votes
1
answer
156
views
How do I get and/or verify a formal Grammar for a given formal Language? [duplicate]
I was given the Language $L=\left \{ a^nb^na^nb^n |n\epsilon \mathbb{N} \right \}$ and I'm supposed to find a Grammar that generates that Language.
After some trying and fiddling I found one that I ...
- 21
0
votes
0
answers
102
views
A context free grammar for the language of even-length non-palindromes [duplicate]
I am trying to find a context free grammar for the language
$L = \{xy \mid |x|=|y| \text{ and } x≠y^R\}$
where $y^R$ is the reverse of string y and $x, y\in \{a,b\}^*$ . Here is a possible ...
- 161
0
votes
0
answers
67
views
How i can use Mathematical induction to prove CFG production? [duplicate]
If I have production $G_n$
$S \rightarrow A_i b_i \quad$ for $1 \le i \le n$
$A_i \rightarrow a_j A_i \mid a_j\quad$ for $1 \le i$ and $i \ne j$
Prove $G_n$ is sub-productions from $2n^2 - n$
...
- 1
-1
votes
1
answer
62
views
Tools or techniques for studying the language a CFG produces? [duplicate]
When developing a CFG, I find that one can be confused about whether the grammar is correct, i.e. whether it recognizes only the required strings and not other strings.
But this can be hard to see?
...
- 567
0
votes
0
answers
50
views
Context free grammar of $ L=\{a^nb^m, n\neq 2m\} $ [duplicate]
I have to find the context-free grammar of this language:
$ L=\{a^nb^m, n\neq 2m\} $
So I did:
$ S \to a \mid aYb \mid \epsilon$
$Y \to aSb \mid X \mid \epsilon$
$X \to bX \mid \epsilon $
is it ...
- 1
0
votes
0
answers
37
views
Context Free Grammar for a language [duplicate]
I have a language L = {a^n b^m c^k | n = m or m != k}
When I was working the problem out this is what I got:
S -> S1|S2
S1 -> AC
A -> aAb|$\lambda$
C -> Cc |$\lambda$
S2 -> BD
B -> aB|$\lambda$
D ->...
0
votes
0
answers
31
views
Grammar that generates a language with more "a" than "b" [duplicate]
I need to find a grammar that generates the language composed by all words that have more $a$ than $b$ given an alphabet $\{a,b\}$
I tried the following production rules:
...
- 2,240
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
28
votes
2
answers
45k
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.♦
- 154k