68 questions linked to/from How to show that L = L(G)?
680 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 ...
42 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: ...
128 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 ...
20 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 ...
24 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 ...
29k 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 ...
31 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.
54 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 ...
45 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 ...
186 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)}. ...
60 views

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,... 0answers 240 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 ... 1answer 95 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 ...
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 ...
### 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 ...