68 questions linked to/from How to show that L = L(G)?
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: ...
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 ...
29 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 ...
36 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.
68 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 ...
50 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 ...
246 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)}. ...
63 views

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 ...
85 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 ...
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 & \...
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 ...
$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 ...