Linked Questions
68 questions linked to/from How to show that L = L(G)?
0
votes
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 more $a$ than $b$ given an alphabet $\{a,b\}$
I tried the following production rules:
...
7
votes
3answers
2k views
Context-free grammar for $L = \{a^{2^k}, k \in\mathbb{N}\}$
In an exercise, I am asked to find a context free grammar for language $L = \{a^{2^k}, k \in \mathbb{N}\}$.
I have been trying to use a "doubling" variable. If $a^{2n} \in L, n\in\mathbb{N}$ then use ...
5
votes
1answer
3k views
Equivalence of two context free grammars [for the given example]
I know that in general it is undecidable whether two context free grammars generate the same language, but I have to do this exercise and I am finding myself somewhat stuck:
G1:
S->e|aB|bA
B->bS|...
5
votes
1answer
195 views
Proof by induction over rules for mutually recursive relations
Consider the (big-step) semantics of a language ($a, e$ terms, $v$ values), defined by two mutually recursive relations, $\downarrow$ and $\Downarrow$, given by a set of rule-schemata (simplified):
$\...
0
votes
0answers
64 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 ...
1
vote
2answers
5k views
Prove correctness of DFA ending with ab
I have the following deterministic finite automaton and I am need to prove correctness of the claim that this automata accepts $\{wab \mid w\in \{a,b\}^*\}$
I know that I need to prove by induction ...
0
votes
1answer
870 views
How do you prove two languages are equivalent using the definition of acceptance?
I need to prove that $L(f(M)) = L(M)\cup \{\varepsilon\}$
where $M$ is a DFA and $f$ is the function $f(M) := (Q\cup \{q_f\}, \Sigma, \delta', q_f, F\cup\{q_f\})$ and $q_f$ is a new state not in $Q$ ...
-1
votes
1answer
1k 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 ...
0
votes
1answer
686 views
How do I use induction to show that the language of a grammar is contained in a given set? [duplicate]
Given that I have the grammar
$\qquad\displaystyle G_1 = (\{a, b, c, d\}, \{S, X, Y \}, S, \{S → XY, X → aXb, X → ab, Y → cYd, Y → cd\})$,
how am I supposed to prove that
$\qquad\displaystyle S(G1) ...
0
votes
1answer
559 views
Regular expression for a binary number that includes “10” and has an odd number of 0's
I have been struggling trying to write a regular expression for a binary number that includes "10" and has an odd number of 0's, so far I have (1) * (00) * 10(1010) * (00) * (1) * but it doesn't ...
1
vote
0answers
579 views
How to describe the language generated by S → a | S + S | S S | S * | ( S )
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\...
1
vote
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 ...
-2
votes
1answer
185 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.
0
votes
1answer
246 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 ...
4
votes
2answers
159 views
Gyorgy E. ReveszExercise 1.1: Show the grammar $G$ generates the language $L$ [duplicate]
The exercise says
"Show that the grammar $G = \langle\{S\}, \{a, b\}, S, \{S \to \lambda, S \to aSb\}\rangle$
generates the language $L = \{a^i b^i \mid i = 0, 1, 2, \ldots\}$."
Now, I'm new to ...