5
$G_1$ and $G_2$ are equivalent if and only if $L_{G_1} = L_{G_2}$.
Since the relation $=$ is an equivalence relation over languages, so is the equivalence between grammars.
5
Usually that is a matter of taste. If I am nathematically motivated then I write $a^*$ like some single argument postfix operations in mathematics. If I keep close to applications, I would type $a*$ because typing superscripts in input for programs seems silly.
Same for $a^+$.
Be aware that in the context of regular expressions plus $+$ might have another ...
4
$\Sigma$ is a (not proper) superset of itself but there are other supersets of $\Sigma$. For example if $\Sigma = \{a,b\}$ and $\Sigma'=\{a,b,c\}$ then $\Sigma'$ is a (proper) superset of $\Sigma$.
To show that the claim is true you just need to show that, for every finite set $\Sigma' \supseteq \Sigma$, you have $(\Sigma')^* \supseteq \Sigma^*$. Then, for ...
4
Yes. What you are constructing is the product automaton recognizing the language $L_{s,q}\cap L_{q,f}$, where for $q, q' \in Q$, $L_{q,q'}$ is the language of words leading from state $q$ to state $q'$. Formally:
$$L_{q,q'} = \{u\in \Sigma^*\mid q'\in \delta^*(q, u)\}$$
It is well known that $L_{q,q'}$ is a regular language (just consider the initial state $...
3
You certainly don't need a context-sensitive grammar to solve this problem (and it probably wouldn't help you, either). In fact, you can solve it with the precedence declarations available in most standard parser-generating tools. For example, a simple bison grammar is:
%left '+'
%left LAMBDA_LEFT
%left APPLY "lambda" VALUE ID '('
%%
expr : expr '+'...
3
"$\lambda$" is commonly used to represent the empty string, although "$\epsilon$" could be the more common one.
This was introduced earlier in that book, section "3.1 Grammar Editing" of chapter "Regular Grammars".
On the last row you will enter the production $A \rightarrow \lambda$, a
$\lambda$-production. To do ...
2
Every rational language can be represented by (at least one) rational expression, and every rational expression represents a rational language. That means for any rational language, you can find the equivalent expression (though it might not always be a simple task). In fact, there are algorithms that convert any NFA into an equivalent rational expression ...
1
Let $\mathcal{G}$ be the set of all context-free grammars and let $\rho \subseteq \mathcal{G}^2$ denote the binary relation "being equivalent to".
Let $G$ be a CFG grammar. Clearly it holds that $G \rho G$ since $L_G=L_G$. Therefore $\rho$ is reflexive.
Let $G$ and $G'$ be CFG grammars such that $G \rho G'$. By definition of $\rho$ we have $L_{G} = ...
1
You missed state $\emptyset$. The transition from state $1$ when character $a$ is read goes to $\emptyset$.
Since all transition from $\emptyset$ also go to $\emptyset$, you can also use the standard convention of omitting $\emptyset$ (and the transition for character $a$ from state $1$).
If a DFA has some missing transitions, it can always be completed by ...
1
A good first step for designing automata is to think about what states you will need. Here, you would need to remember the sum – which is not possible with a DFA – but thankfully, we only need to remember the sum in mod3 arithmetic, which means it can only have three distinct values: 0, 1 or 2. Therefore, we can keep track of the sum mod 3 with a finite ...
1
Your DFA doesn't match the empty string.
Note that if $L$ is regular, then infinitely many DFAs accept $L$. There is no unique answer for "DFA that accepts $L$". However, there is a canonical answer: there is a unique DFA with the minimum number of states that accepts $L$, known as the minimal DFA. Your teacher drew the minimal DFA for your ...
Only top voted, non community-wiki answers of a minimum length are eligible