# Tag Info

2

First notice that $L_1$ is really simple: $$L_1=\{w^* \mid w=x\text{ and }x \in \Sigma^*\}\supseteq\{w^1 \mid w=x\text{ and }x \in \Sigma^*\} =\Sigma^*$$ Hence $L_1=\Sigma^*$. Then notice that$L_3$ is also really simple: $$L_3=\{w \mid w=x.y, x,y \in \Sigma^*, y\text{ is a sub-string of }x\}$$ If as sub-string you allows $\epsilon$, then you van ...

2

Hint: Draw a state machine with four states: $\boxed{S_{0,0}}$: This is the initial and only accepting state. If you're here, then there is an even number of both $a$'s and $b$'s. $\boxed{S_{0,1}}$: If you're here, then there is an even number of $a$'s and an odd number of $b$'s. $\boxed{S_{1,0}}$: If you're here, then there is an odd number of $a$'s and ...

1

The grammar $G_1$ is ambiguous because there are two left-most derivations for the string "()". The first is $S\to SS\to (S)S\to ()S \to ()$, and the second is $S\to(S)\to()$. The grammar $G_2$ is not ambiguous. First, we can see that $L=\mathcal{L}(G_2)$ is the set of well-parenthesized strings (like "(()(()))()"). There are a few ways to prove this, ...

1

Popular tool for proving a language is not context-free is the Pumping Lemma. Let's recall its statement: If $L$ is a context-free language, there exists $p\geq 1$ such that each $s\in L$ with $\left|s\right|\geq p$ can be written as $$s=xuyvz$$ in such a way, that $\left|uyv\right|\leq p$ $\left|uv\right|\geq 0$ (i.e. at least one of $u$, ...

1

The following conforms to your request to just "fill in the boxes", but technically there is an arrow for each of the three items in box 2, all pointing to state c. Also, I think the given portion of your diagram implies rather non-standard input/output conventions. Assumptions: $\text{div}$ denotes integer division; i.e., $\ \ x \text{ div } 2 \ = ... 1 This is a good example of how bad notation can make simple questions much more difficult. (1) There is no reason to introduce grammars. You may as well denote by$L_1$the language accepted by$M_1$and by$L_2$the language accepted by$M_2$. (2) Let us denote by$L^c$the complement of a language$L$. Then your first (correct) equality amounts to prove ... 1 p-regular languages are commonly known as (regular) group languages in the literature since their syntactic monoid is a finite group. If a language is accepted by a permutation automaton, then its minimal DFA is also a permutation group, but this group is transitive (since every state is accessible from the initial state). Thus your subclass is actually ... 1 If I'm not missing something, then strings generated by option 3 must always end with a$\mathtt{1}\$ while for the regex in question this is not necessary. So I'd agree with you that option 3 doesn't seem to be the right answer.

Only top voted, non community-wiki answers of a minimum length are eligible