New answers tagged

0 votes

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 ...
gnasher729's user avatar
  • 28.4k
-1 votes

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
setiawan jodhi's user avatar
0 votes

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 ...
Hendrik Jan's user avatar
  • 29.8k
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.
J.-E. Pin's user avatar
  • 6,014
0 votes
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 ...
ratchet freak's user avatar
0 votes

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). ...
gnasher729's user avatar
  • 28.4k
0 votes
Accepted

How to find prefixes and suffixes for infinite languages? (Automata)

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, \...
Kai's user avatar
  • 663
0 votes

How to find prefixes and suffixes for infinite languages? (Automata)

Let's see what others say but I think you could adapt the algorithm that enumerates the sentences of a language and restrict it to enumerate prefixes or suffixes only. I assume you are familiar with ...
Chaos's user avatar
  • 463

Top 50 recent answers are included