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 ...
- 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
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 ...
- 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.
- 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 ...
- 4,301
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).
...
- 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, \...
- 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 ...
- 463
Top 50 recent answers are included