# Linked Questions

67 questions linked to/from How to show that L = L(G)?
1answer
94 views

### Finding the language generated for CFG

What language generated by the following context-free grammar 1) S------> SaS | b i already know the answer to question one but to prove it would is be something like this: S -----> SaaS -----> baab ...
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 ...
1answer
178 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.
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 ...
0answers
168 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 ...
0answers
46 views

### What are resources that I can use to learn about formal langauges?

What are some good resources for practice problems on formal languages? Every textbook I've seen contains few practice problems with even fewer answers. I would like a resource that has questions with ...
0answers
544 views

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\... 0answers 92 views ### Does this grammar generate regular language?$S \rightarrow ABA \rightarrow aA \mid bA \mid \epsilonB \rightarrow aBb \mid \epsilon$Does this grammar generate regular language? According to me this grammar generates language of the ... 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'... 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 ->... 0answers 253 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 ... 0answers 570 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 \... 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 morea$than$b$given an alphabet$\{a,b\}$I tried the following production rules: ... 0answers 58 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 ... 0answers 59 views ### How i can use Mathematical induction to prove CFG production? [duplicate] If I have production$G_nS \rightarrow A_i b_i \quad$for$1 \le i \le nA_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\$ ...

15 30 50 per page