New answers tagged finite-automata
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 ...
-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
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 ...
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.
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 ...
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).
...
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, \...
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 ...
Top 50 recent answers are included
Related Tags
finite-automata × 1738automata × 798
regular-languages × 530
formal-languages × 319
regular-expressions × 288
nondeterminism × 140
turing-machines × 81
pumping-lemma × 65
algorithms × 61
context-free × 59
pushdown-automata × 59
computability × 55
closure-properties × 54
complexity-theory × 50
formal-grammars × 48
computation-models × 40
proof-techniques × 33
compilers × 29
terminology × 22
reference-request × 22
simulation × 21
undecidability × 20
transducers × 16
graphs × 14
strings × 14