10
votes
Accepted
Do all instances of a given string get replaced under a rewrite rule?
Probably your course teaches the context-free grammar. Indeed, in a CFG one position in the string is chosen, and the symbol at that position is rewritten using one of the rewrite rules.
In a CFG the ...
- 30.9k
5
votes
Accepted
Give a class of languages which is closed under intersection and union, but not under complement
An example of a class of languages which is closed under union and intersection, but not under complement is the class of finite languages.
Context-free languages are closed under union, but not under ...
- 30.9k
1
vote
Detect (indirect) left-recursion in a context-free grammar?
You can solve that by modelling the recursions.
Make a graph, where $A$ points to the beginning symbols of the $\alpha$'s. Etcetera.
Then detect cycles in that graph.
I have no clue whether the ...
- 30.9k
1
vote
Do all instances of a given string get replaced under a rewrite rule?
Rewriting systems usually apply each rule once, sequentially. The left hand side might match at several points, in which case any match could be taken,
- 14.1k
1
vote
Proving that two languages both represent valid bracket sequences
Prove by induction that if $w\in L_2$ then $0w1 \in L_2$.
Case $w = 01$, we want to prove $0w1 \in L_2$. Indeed, we start with $01 \in L_2$, and then use the second rule with $w_1 = 0$, $w_2 = 1$. ...
- 685
Only top scored, non community-wiki answers of a minimum length are eligible