Linked Questions
68 questions linked to/from How to show that L = L(G)?
1
vote
1answer
44 views
Regular expressions
I am new to theoretical cs and am working through it slowly. I have completed a simple question and was wondering if my answer is correct or not. Thank you kindly for any feedback.
The question is:
...
-1
votes
1answer
30 views
How can I prove that the accepted language of a given DFA or NFA or REGEX is equivalent to a given language
I found this How do I verify that a DFA is equivalent to a NFA? but as it states it is not really a good question more of how can I check myself during an exam. Because as you might know to do this by ...
0
votes
1answer
27 views
A grammar for my context free language {xy | x, y ∈ {a, b} ∗ , |x| =|y| , x != y}
This question is given as an exercise to me . I took a look at the solution given by the instructor which is not the same as my solution .
So I thought it would be wise to ask it here considering ...
-1
votes
1answer
34 views
What is the language generated by this grammar?
I'm struggling to find the language generated by the following grammar:
Any help would be appreciated.
1
vote
2answers
64 views
Is my grammar correct and context free?
I have this language
$L = \{a^{n}b^{3n}c^{2m} : m,n \ge 1\}$.
I have to determine a free context grammar that generates L.
Looks easy BUT i have a question about the grammar I found.
First things ...
0
votes
1answer
48 views
Language to regex
Let A={a,b}.
So the question is to write regular expression such that L(r) which consists of all words.
My answer is this:
L(r)= (a+b)* a* b* (a+b)*
Is this ...
2
votes
1answer
236 views
Proving that L(G) is the language defined by the CFG G
I have a context-free grammar defined by the production S:
S → aSbS ∣ bSaS ∣ ε
I need to prove that the CFG "G" can be defined as a language L(G) where
L(G) = {w ∈ {a, b}∗ ∶ na(w) = nb(w)}.
...
-1
votes
1answer
61 views
Find the language from a context free grammar
I am having trouble determining the language from a given context free grammar. I've been given a hint that there are 2 parts to the language but can't figure either out.
$$G= (\{S,A,B,C,D,E,Z\},(0,...
2
votes
2answers
442 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 ...
2
votes
1answer
98 views
How to produce a context free grammar for this language?
I've already attempted it but I am finding it difficult to understand if this is correct.
give a context free grammar for the following:
$$ \{p^{3m+n}q^nr^2p^m\mid m,n\ge 0 \}$$
The answer i've ...
2
votes
0answers
241 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
84 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 ...
0
votes
2answers
169 views
Removing epsilon transition from the grammar. What's the difference between accepting languages?
I want to remove the epsilon transition from following grammar:
\begin{eqnarray}
S & \rightarrow & A | B \\
A & \rightarrow & \epsilon \\
B & \rightarrow & aBa \\
B & \...
1
vote
3answers
848 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 ...
0
votes
0answers
92 views
Does this grammar generate regular language?
$S \rightarrow AB$
$A \rightarrow aA \mid bA \mid \epsilon$
$B \rightarrow aBb \mid \epsilon$
Does this grammar generate regular language?
According to me this grammar generates language of the ...
0
votes
2answers
438 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)$. ...
1
vote
1answer
366 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 \...
0
votes
0answers
47 views
Is this language equivalent to this grammar?
The book that I'm reading says it is equivalent
But what about the aa string ? i produce it this way :
$$
S\Rightarrow S_1B\Rightarrow aS_1bB\Rightarrow aaB\Rightarrow aa
$$
But that language doesn'...
2
votes
1answer
3k 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
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
121 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?
2
votes
1answer
133 views
Language of CFG: $S \to aS | aSbS | \varepsilon$
I'm trying to prove that the language L generated by the CFG $S \to aS | aSbS | \varepsilon$ is the language $L=\{ w \in \{a,b\}^*: \text{every prefix of $w$ has at least as many $a$'s as $b$'s} \}$.I ...
-1
votes
1answer
3k 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?
0
votes
0answers
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 ->...
2
votes
1answer
362 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 ...
1
vote
0answers
264 views
Regular Expression for All strings which contain no runs of a's of length greater than two.On L={a,b,c} [closed]
My attempt is
We can fairly easily build an expression containing no a, one a, or one aa:
(b+c)(€+a+aa)(b+c)
but if we want to repeat this, we need to be sure to have at least one non-a between ...
1
vote
1answer
261 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 ...
4
votes
1answer
732 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
1k 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 ...
0
votes
2answers
965 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)$?
...