Linked Questions
68 questions linked to/from How to show that L = L(G)?
-2
votes
1answer
121 views
$L = \{ w \in \{0, 1, 2\}^*: |0| + |2| = |1| \}$ where |0| denotes number of 0s in the string w
I have come up with:
S→0SX | 1SY | 2SZ | SS | ϵ
X→1
Y→0 | 2
Z→1
I think I am wrong. Any directions?
-2
votes
1answer
105 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 ...
-2
votes
1answer
187 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.
2
votes
0answers
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 ...
1
vote
0answers
261 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 ...
1
vote
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 ...
1
vote
0answers
580 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\...
0
votes
0answers
92 views
Does this grammar generate regular language?
$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 ...
0
votes
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'...
0
votes
0answers
37 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 ->...
0
votes
0answers
339 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 ...
0
votes
0answers
594 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 \...
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:
...
0
votes
0answers
65 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 ...
0
votes
0answers
62 views
How i can use Mathematical induction to prove CFG production? [duplicate]
If I have production $G_n$
$S \rightarrow A_i b_i \quad$ for $1 \le i \le n$
$A_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$
...