New answers tagged

1 vote
Accepted

Proof that nondeterministic TM runs in exponential time

Assuming $k$ is represented in binary, it takes $\lg k$ bits to represent $k$. So an algorithm whose running time is $\Theta(k)$ runs in time that is exponential in the length of the input. "...
D.W.'s user avatar
  • 158k
0 votes

NFAs that accept a regular language

The language of an NFA $A$, denoted $L(A)$, is the set of words $w$ such that there is an accepting run of $A$ on $w$. Hence, when we claim that an NFA $A$ recognizes a language $L$, we mean that $L(A)...
Bader Abu Radi's user avatar
6 votes

Notation in NFA, DFA diagrams and language

Consider a finite nonempty alphabet $\Sigma$. The set $\Sigma^* = \bigcup\limits_{n\geq 0 } \Sigma^n$ is the set of finite words over $\Sigma$, indeed, for all $n\geq 0$, we define $\Sigma^n$ as the ...
Bader Abu Radi's user avatar
8 votes

Notation in NFA, DFA diagrams and language

You need to distinguish between three kinds of operations: Operations on numbers such as 0 and 1. $0^3 = 0$ when $0$ is taken to be a number. Here, $0^3 = 0 ⋅ 0 ⋅ 0$, where $⋅$ is integer ...
reinierpost's user avatar
  • 5,499
5 votes

Notation in NFA, DFA diagrams and language

For a (usually finite) set $A$ the star denotes the free monoid on $A$ where $$A^* = \{a_1a_2...a_k : k \geq 0 \land \forall i. a_i \in A\}$$ is the set of all finite sequences or strings of elements ...
Knogger's user avatar
  • 710
2 votes
Accepted

Why can't we prove closure under concatenation using DFA?

My only copy of Sipser is the third edition. Here is the relevant quote, after Theorem 26, closure under concatenation of the regular languages. To prove this theorem, let’s try something along the ...
Hendrik Jan's user avatar
  • 30.5k

Top 50 recent answers are included