# Tag Info

### Create DFA such that every substring of w of length 3 contains two or three 0's with w={0,1}

You need seven states: The error state - once in the error state you always go to the non-accepting error state. States 00, 01, 10, 11: These are the last two characters processed. If we process 0 ...

### Create a Deterministic Finite Automaton for a regular expression

Tentukan Bahasa regular dan gambarkan Finite Automata dari Regular ekspresi berikut : a. a (ba)* b. (ab)* a

### Create DFA such that every substring of w of length 3 contains two or three 0's with w={0,1}

An automaton should come with a plan. What is stored or represented in each of the states? When the requirement asks us to check all substrings of a certain length the plan might start with a ...
1 vote

### DFA for even concatenation of strings from a language

The language you are considering is $(W^2)^*$, so you could combine standard constructions for the concatenation and the star operation.
Accepted

### Why does lexer has O(n) time complexity?

Your assumption of execution is based on a suboptimal backtracking implementation based on NFA needing to explore all paths through it. A more optimal implementation would have a bitset of all states ...

### Why does lexer has O(n) time complexity?

If you wrote a lexer for C++ and the next character is an “a” then the token is asm, auto or an identifier. Three choices only. Processing an identifier with a length k should take no more than O(k). ...
For regular languages this is relatively straighforward. Let $L\subseteq\Sigma^*$ be regular. Let $A = (Q, \Sigma, q_0, \delta, F)$ be an NFA that recognises $L$. Construct another NFA \$A' = (Q, \...