Linked Questions
62 questions linked to/from How to show that L = L(G)?
3
votes
2answers
5k 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 ...
-1
votes
1answer
1k 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 ...
0
votes
1answer
572 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) ...
0
votes
2answers
619 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 ...
4
votes
2answers
156 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 ...
2
votes
1answer
98 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 ...
0
votes
0answers
138 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 ...
0
votes
0answers
55 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 - ...
0
votes
0answers
54 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 ...
-1
votes
1answer
48 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?
...
0
votes
0answers
35 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
0answers
22 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:
...
25
votes
4answers
21k 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 } ...
26
votes
2answers
25k 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 ...
6
votes
3answers
1k 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 ...
3
votes
2answers
2k views
Proving that a word is *not* generated by a context-free grammar
I saw the answer in one of the solutions and I cannot figure out how they got the answer. The question is asked if the word is in the language or not for CNF...
How did they get the answer so that ab ...
1
vote
2answers
4k views
Prove correctness of DFA ending with ab
I have the following deterministic finite automaton and I am need to prove correctness of the claim that this automata accepts $\{wab \mid w\in \{a,b\}^*\}$
I know that I need to prove by induction ...
2
votes
3answers
1k views
Why is the distinction between linear and context-free grammars useful?
The linear grammar is a grammar that's either left, right or left and right linear.
The context-free grammar can contain any kind of productions of non-terminals and terminals.
All linear grammars ...
5
votes
1answer
2k views
Equivalence of two context free grammars [for the given example]
I know that in general it is undecidable whether two context free grammars generate the same language, but I have to do this exercise and I am finding myself somewhat stuck:
G1:
S->e|aB|bA
B->bS|...
0
votes
1answer
1k views
PDA or CFG for language $L= \{a^ib^j | 2i \leq 2j \leq 3i, i>0\}$
Can someone help with this
$L= \{a^ib^j | 2i \leq 2j \leq 3i, i>0\}$
2
votes
1answer
2k views
Is the language of all non-palindromes context-free?
Is the language $L = \{ w \mid w \in (a,b)^* \wedge w \text{ is not a palindrome} \}$, context-free? I think this grammar:
$
S \rightarrow aSa \mid bSb \mid aAb \mid bAa\\
A \rightarrow aAa \mid bAb \...
0
votes
1answer
2k views
Is my proof for a context free language correct? Same number of a's as b's
I have the following grammar G:
$$
\begin{align*}
&S \to aB|bA \\
&A \to a|aS|bAA \\
&B \to b|bS|aBB
\end{align*}
$$
I am going to prove that this language L(G) consists of words with the ...
-2
votes
1answer
2k views
Why is the language of even-length non-palindromes context-free?
We know $L_1=\{w_1 w_2 \in (a+b)^*\mid |w_1|=|w_2|, w_2 \neq w_1^{\;\mathrm{R}}\}$
is a context-free language.
Can anyone help me produce a PDA or give me any hint how I can quickly understand why ...
3
votes
2answers
241 views
Figuring out the language of a non-linear CFG
I have the CFG G with the following production rules:
$$
S \to aSaS \mid b
$$
Is it possible to find $L(G)$? I have no idea how describe it by any pattern. I use grammophone to check example words, ...
-1
votes
1answer
2k views
Describing language generated by grammar
S -> aSb | A | B
A -> aS | a
B -> Sb | b
is this the language generated by this CFG? Or am I missing something?
1
vote
1answer
858 views
Proving grammar only generate strings that is multiple of 3
Hello I have an exercise for homework and I was hopping to get some hints in order to solve it.
num-> 11 | 10 num' 01 | num 0 | num num
num'-> 00 num' | 1 num' | ε
I need to prove that my ...
0
votes
2answers
695 views
Finding Language of a CFG
Say you are given the following CFG $G$:
$$
S \to S_1 \mid S_2 \\
S_1 \to AbAS_1c \mid \epsilon \\
S_2 \to BaBS_2c \mid \epsilon \\
A \to Aa \mid \epsilon \\
B \to Bb \mid \epsilon
$$
What is $L(G)$?
...
4
votes
1answer
539 views
Finding the language of a context-free grammar?
Given following question:
Let $G$ be a context-free grammar, $G=(V, \Sigma, R, S)$, that has start
variable $S$, set of variables $V = \{S\}$, set of terminals $\Sigma = \{0, 1\}$, and set of rules $...
0
votes
2answers
364 views
Regular expression $(a^{*}b^{*})^{*} = \left( a+b \right)^{*}$ proof
Im having a lot of trouble proving that for the Regular expression $R_{1} = \left( a^{*} b^{*} \right)^{*}$ and $R_{2} = \left( a+b \right)^{*}$ that $L \left( R_{1} \right) = L \left( R_{2} \right)$. ...
0
votes
1answer
734 views
How do you prove two languages are equivalent using the definition of acceptance?
I need to prove that $L(f(M)) = L(M)\cup \{\varepsilon\}$
where $M$ is a DFA and $f$ is the function $f(M) := (Q\cup \{q_f\}, \Sigma, \delta', q_f, F\cup\{q_f\})$ and $q_f$ is a new state not in $Q$ ...
2
votes
2answers
259 views
Proof for BFS and DFS equivalence
I'm trying to prove (by induction) that BFS in equivalent to DFS, in the sense that they return the same set of visited nodes, but I'm stuck in the middle of some of the cases.
Let $G$ be a directed ...
4
votes
3answers
238 views
Designing a CFG that produces as many c's as the difference of numbers of a's and b's
The question is to design a CFG for the language of words that have as many c's as the difference of numbers of a's and b's, that is
$\qquad\displaystyle L = \{(a^l)(b^m)(c^n) \mid l, m \in \mathbb{N}...
2
votes
1answer
601 views
Show that language generated by grammar is regular
We have grammar with nonterminals $ X_1,...X_n$ terminals $V_t$ and rewriting rules of form:
$X_i \rightarrow a \in V_t $
$X_i \rightarrow X_jX_k, \ i \ge j , \ i > k $
How can I show that ...
0
votes
2answers
810 views
Context-free grammar for“not-at-all” palindromes
I need to bulid a context-free grammar for
$\qquad \mathscr{L_4}=\{w\in\{a,b,c\}^* \mid w\text{ is not palindrome at all}\}$
Not palindrom at all:
We will say that a word $w$ is not palindrome at ...
0
votes
1answer
479 views
Regular expression for a binary number that includes “10” and has an odd number of 0's
I have been struggling trying to write a regular expression for a binary number that includes "10" and has an odd number of 0's, so far I have (1) * (00) * 10(1010) * (00) * (1) * but it doesn't ...
1
vote
0answers
535 views
How to describe the language generated by S → a | S + S | S S | S * | ( S )
I am trying to solve the following problem from Aho, et al., Compilers: Principles, Techniques, & Tools (2nd ed.), exercise 2.2.2e:
What language is generated by the following grammar? $S\...
0
votes
0answers
501 views
Describe the language generated by a given context free grammar
I had an exercise: Describe the language generated by the following given context free grammar and prove it by induction.
$$\begin{align}
S &\to SA \mid \epsilon \\
A &\to aS \mid bA \...
5
votes
1answer
182 views
Proof by induction over rules for mutually recursive relations
Consider the (big-step) semantics of a language ($a, e$ terms, $v$ values), defined by two mutually recursive relations, $\downarrow$ and $\Downarrow$, given by a set of rule-schemata (simplified):
$\...
1
vote
3answers
445 views
Context-free grammar for binary words
I am supposed to create CFG for this languague:
$L= \{w : w \in \{a, b\}^*, |w_b| = 3k, k \geq 0 \}$
where $|w_b|$ is count of terminals $b$ in $w$.
For example:
aa - OK, no 'b'
abb - wrong, only ...
1
vote
2answers
193 views
Show that a language cannot be generated by linear grammar
I have a language $ L= \{ w \in \{a,b\}^* ; |w|_b=2i, i \ge 0 \}$ that is a language with even number of b's.
I found a grammar for it with these rules:
$S \rightarrow aS \ | \ bL \ | \ \lambda $...
1
vote
1answer
310 views
Determining Language from Context Free Grammar
I am trying to understand how to write the language given the predicates of the context free grammar. As an example, I have the following grammar:
$S \to 0B \mid 1A$
$A \to 0 \mid 0S \mid 1AA$
$B \...
2
votes
1answer
284 views
Prove the equivalence between a CFG and a Context free language
I have to prove that the language $L=\{a^ib^j:2i=3j+1\}$ and the CFG G with the following rewrite rules:
$S\rightarrow a^2Tb$
$T\rightarrow a^3Tb^2 |\epsilon$
are equivalent to each other.
I'm ...
0
votes
1answer
261 views
Why is this language not context free?
I been watching tutorials about how to check if a language is not context-free and in 1 video there was a language: L = {a^n b^n c^n | n ≥ 0} and they used a pumping lemma to prove that it's not ...
1
vote
1answer
221 views
Prove L = L(R) based on a regular expression
I'm given the following language:
L = {w∈{0,1}* | w ends in 010 and contains 011}
The task is to find a regular expression R that describes this language and ...
0
votes
1answer
153 views
A DFA recognizing my name
How can I know if my DFA is implemented correctly?
For example, I need to build a DFA, and then minimize it which will recognize my name.
Language which describe my name is:
L = {pustai, marius}
I ...
2
votes
2answers
69 views
Interpreting a Language
I'm having trouble understanding some language notation, primarily what rules I can take away from it. The language is as follows:
$\qquad L = \{a^n b^m b^p c^p b^{n-m} \mid n > 0, m < n, p >...
2
votes
0answers
237 views
Context-sensitive grammar for language $L = \left\{ww \mid w \in \left\{a,b\right\}^* \right\}$ [duplicate]
Find a context-sensitive grammar for language $L = \left\{ww \mid w
\in \left\{a,b\right\}^* \right\}$ where $L \in DCSL \setminus CFL$.
I find this task from old exam but there is no solution. I try ...
-2
votes
1answer
165 views
Find an unambiguous grammar [closed]
S → aS | aSbS | (empty)
where the alphabet is {a,b}
in other words, the set of strings where any prefix has at least as many 'a's as 'b's.
2
votes
1answer
77 views
Proving $L = \{ w : w \neq w^R \}$ over $\Sigma = \{0,1\}$ is CFL
I'm trying to prove $L = \{ w : w \neq w^R \}$ over $\Sigma = \{0,1\}$ is CFL.
Define $G = ({S,T}, \Sigma, R, S)$ where $R = S \to 0S0|1S1|0T1|1T0, \; T \to 0T|1T|\varepsilon$.
Now I want to show ...
-2
votes
1answer
118 views
$L = \{ w \in \{0, 1, 2\}^*: |0| + |2| = |1| \}$ where |0| denotes number of 0s in the string w
I have come up with:
S→0SX | 1SY | 2SZ | SS | ϵ
X→1
Y→0 | 2
Z→1
I think I am wrong. Any directions?