Tag Info

New answers tagged

0

4 has to be correct, as the empty string is in $0^*(10^*)^*$ but not in 1, 2 or 3.


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.


0

Yes every NFA has a corresponding DFA, the process of constructing the DFA from the NFA is called subset construction. In essence each state of the DFA is a set of states of the NFA. The constructed DFA recognizes the same formal languange as the starting NFA.


0

Yes, that's correct. An NFA is allowed to be in multiple states in once and can have multiple initial/accepting states. It doesn't have to be though; we can construct an NFA to be in only one state at any point in time and have only one initial and one accepting state, so that it is the same as a DFA. In fact, DFAs and NFAs are actually equivalent. As Brian ...


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 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

Try the following: The formatting isn't perfect. But the idea is to loop until you find a $c$, then try to find a $cdc$. If you don't find the correct next character, go back and start over. Once you find a $cdc$, move to the other (left) half of the diagram and do it all again. Once you've found the second $cdc$, accept. The rest of the string is ...


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 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

The regular expression tells us that the language accepted is either an 'a' and then any number of 'b's or a non-zero number of 'b's. It's not hard to see that any such string will be accepted by the NFA (after 'ab' or a single 'a' we have states 2 and 3 active in the NFA and then the bs just cycle them around.) Additionally, the empty string isn't accepted. ...


0

I'm not sure what your transition notation is for the automaton, but approaching it just as a "What's the odd grammar out?" question: We can inline to get $S \rightarrow aSaa \mid aa \mid a$ and see that the language it generates is $L_1 = \{ a^n \mid n \not\equiv 0\pmod 3\}$ We can rewrite as $S \rightarrow aC$, $C \rightarrow aaC \mid \varepsilon$ and ...


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 ...


0

Yes you're attempt seems fine. Try also to write it down formally, so that it is a direct application of the definition. I would just omit the empty string, since $e0=0$. The way you write it just makes it harder to read and understand.


0

Let $A$ be the alphabet and let $B = \{[a_1a_2] \mid a_1, a_2 \in A \} $. Let $\alpha, \beta: B^* \to A^*$ be the monoid homomorphisms defined by $\alpha([a_1a_2]) = a_1a_2$ and $\beta([a_1a_2]) = a_2a_1$, for each letter $[a_1a_2]$ of $B$. Now $L' = \beta(\alpha^{-1}(L))$. Since regular languages are closed under homomorphisms and inverses of homomorphisms, ...


0

How about $S \rightarrow aSA \mid bS \mid \varepsilon$ and $A \rightarrow b \mid aA \mid \varepsilon$? Disclaimer: I didn't think about this for more than ten seconds, so please check!


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

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 ...



Top 50 recent answers are included