Skip to main content
6 votes

Are there infinite state machines, and how do their computational power relate to turing machines?

Turing machines aren't defined this way simply because automata with an infinite number of states aren't effective. The definition of effective procedures tries to capture our intuitive understanding ...
Knogger's user avatar
  • 1,032
4 votes
Accepted

A context-sensite grammar for the language of sequences of two different types of parentheses with possible intersections?

Basically, the idea is that $($ and $)$ can commute with $[$ and $]$, but $($ cannot commute with $)$ – and same for $[$ and $]$. An essentially noncontracting grammar would be: $S \to \varepsilon \...
Nathaniel's user avatar
  • 15.6k
3 votes

NFA for a regular expression without $\epsilon$-transitions

You can convert the regular expression into an automaton using the Glushkov's construction. The resulting automaton is non-deterministic and does not contain any $\varepsilon$-transition. Its number ...
Nathaniel's user avatar
  • 15.6k
3 votes

Is matching pairs sufficient?

I assume that the Turing machine $M$ is allowed to be nondeterministic. In that case we need three positions. Consider the possibility that $M$ on a certain configuration may move either left or right....
Hendrik Jan's user avatar
  • 30.7k
2 votes
Accepted

Regular languages: words from A that do not contain any word from B as a substring

Your language is $A$ intersected with $$\{w\mid \not\exists y\in B\ :\ w=xyz\text{ for some }x,z∈Σ^∗\},$$ i.e., the complement of $$\{w\mid\exists y\in B\ :\ w=xyz\text{ for some }x,z∈Σ^∗\}$$ which is ...
user6530's user avatar
  • 934
2 votes
Accepted

NFA for $L = \{\sigma_1 u \sigma_2 v \sigma_3 \mid (\sigma_1, \sigma_2, \sigma_3 \in \Sigma, u, v \in \Sigma^*, |u| = |v|) and ...$

It is indeed regular. Here, your language is basically $1(0+1)^{2m+1}0 + 0(0+1)^{2m+1}1$ for all integers $m \ge 0$. We are basically fixing $\sigma_1 \ne \sigma_3$, and then let $|u\sigma_2v|$ be an ...
codeR's user avatar
  • 706
2 votes
Accepted

Regex for $L = \{ w \mid w \in \Sigma^* \text{ and each substring } u \text{ of } w \text{ where } |u| = 4 \text{ contains the character } 0 \}$

Basically, your language asks you to restrict the run length of 1s to at most three. Here's how you can construct the required regex: Step 1: Construct a DFA $M$ that accepts all strings that have at ...
codeR's user avatar
  • 706

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