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