4

There is clearly no sublinear-time algorithm; any algorithm needs to look at all words in the input to have a hope of being correct. There is a straightforward algorithm to construct a trie that recognizes these words in linear time. The trie is a DFA, but not a minimal DFA. The trie is acyclic, and apparently there are algorithms for minimizing an ...


4

You can use either way. In both cases you construct a mapping from the states of the automaton to regular expressions, $[-]: Q\to RE$. Let $(s, l, t)$ denote a transition from $s$ with label $l$ to target state $t$. Also, let $\oplus_{i\leq n}r_i = r_1 + \ldots + r_n$. 1st case: By incoming edges. Add a final state, $F$, and an $\varepsilon$-transition ...


3

There are many possible distance metrics, and without any criteria, we have no basis to choose. Here are two plausible ones. Let $L_1,L_2$ be the languages of the two DFAs. Let $L$ be the symmetric difference of those languages (i.e., $(L_1 \setminus L_2) \cup (L_2 \setminus L_1)$). One dissimilarity measure is $d(L_1,L_2) = 2^{-n}$ where $n=\min\{|x| : ...


3

The answer depends on whether $L_1$ is a language over $\{a,b\}$ or over $\{a,b,c\}$. $L_1$ is a language over $\{a,b\}$ In this case, the easiest way to proceed is using closure operations. Show first (by constructing a DFA) that the following language is regular: $$ L_2 = \{wcv \mid |w|_a+2|v|_b \equiv 3 \bmod 5 , w,v \in \{a,b\}^*\}. $$ Your language is ...


2

The claim that a DFA does not have memory is incorrect, a DFA in fact has finite "memory" in the sense that you can design the states to have meanings in terms of some variables. (Eg. being in state 5 means you've seen at least 5 a's, so you in some sense remember that you've seen 5 a's) Now to address the question, starting at the state marked S and ...


2

Imagine writing a program on any high-level language for checking if string corresponds the given restriction. You would probably iterate symbols one by one and check if appending next symbol breaks the restriction. Now note that you need only two last symbols to do it, and there are finite number of two-symbols combinations (namely $--, -0,-1,00,01,10,11$...


1

For every $i=0,\dots,4$, there exists a regular expression $W_i$ for the language of all words $w$ such that $|w|_a \bmod 5 = i$. For example: $$ ((b+c)^*a)^i ( ((b+c)^*a)^5)^*(b+c)^* $$ Similarly, for every $j=0,\dots,4$, there exists a regular expression $Z_j$ for the language of all words $z$ such that $2|z|_b \bmod 5 = j$. Then a regular expression ...


1

First construct the DFA which accepts any string that DOES contain "abaa". Then interchange final vs non-final! (note: this only works with a DFA, not an NFA) The rest you have already figured out.


1

Can you please suggest is it possible to do it with FSM (Moore or Mealy machine) The machine you are looking for is called a finite-state transducer. They can be defined in either Moore or Mealy variants. For the Mealy variant (which I believe is more common), you have a finite state machine where the edges are labeled with output, and the initial states ...


1

This is not an answer, but too long for a comment. so far I have not come across any applications in computer science. This surprises me, for the two following reasons: The Thue-Morse sequence is automatic, i.e., the sequence is fully characterized by a finite automaton, It is a binary sequence. You may want to refine your criteria for what ...


1

Use nondeterminism to guess an index $i$ for which $w_i \neq w_{i+1}$. The machine reads its input until it nondeterministically chooses a $w_i$ and places it on the stack. Afterwards, it compares $w_{i+1}$ to the content on the stack symbol by symbol. If the comparison fails, the machine accepts.


1

(1∗01∗01∗)∗ is actually wrong because it doesn't handle a string consisting of all 1's


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