# Linked Questions

71 questions linked to/from How to show that L = L(G)?
2answers
7k 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 ...
2answers
2k 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 ...
1answer
2k 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 ...
1answer
739 views

1answer
390 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 ...
1answer
370 views

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 \... 1answer 281 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 ... 1answer 215 views ### How to prove a L=L(G) without knowing the L? [closed] How does one prove L(G)=L if the language is not given and only the grammar G is given? If there is no pattern to be seen in the grammar that would create the strings w of a language L, how would you ... 1answer 320 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)}. ... 1answer 299 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 ... 1answer 273 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 ... 0answers 303 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 ... 1answer 194 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. 2answers 70 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 >...

15 30 50 per page