309 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
1
vote
1
answer
112
views
How to build DFA with subset construction algorithm when NFA contain `.` condition
such as .*ab
For this regex, I can build an NFA using the Thompson algorithm like:
When I try to use the subset construction algorithm to change it to a DFA, I find the result is weird.
the DFA ...
-4
votes
1
answer
3k
views
Design NFA that accepts strings starting with a and ending with a or starting with b and ending in b
Also is regular expression possible for it? If yes, can someone show me both RE and NFA for this question?
This is the NFA that I designed, but I am not really confident about my answer.
NFA - ...
1
vote
1
answer
88
views
Cannot convert NFA code in Algorithm course in Java to C++ [closed]
I've learned Coursera Algorithm course, and I want to convert NFA code in Java of this course to C++ by myself.
Here's my code:
DirectedGraph.h:
#ifndef DIRECTEDGRAPH_H
#define DIRECTEDGRAPH_H
#pragma ...
0
votes
1
answer
54
views
Theory of Comp Sci - State Diagrams NFAs
I have been given this theorem and example that goes with it:
Theorem 1.49
The class of regular languages is closed under the star operation.
PROOF IDEA We have a regular language A1 and want to ...
0
votes
1
answer
112
views
Theory of computer science problems
I am working on theory of computer science problems but cannot get these to work:
a. Give an NFA recognizing the language (01 ∪ 001 ∪ 010)*
b. Convert this NFA to an equivalent DFA. Give only the ...
1
vote
1
answer
893
views
State diagram of DFA with 5 states
Let F be the language of all strings over {0,1} that do not contain a pair of 1s that are separated by an odd number of symbols. Give the state diagram of a DFA with five states that recognizes F . (...
0
votes
1
answer
1k
views
Conversion of NFA having a missing transition for any input character on initial state to DFA
I was practicing NFA (Non-Deterministic-Finite-Automata) designing and converting them to DFA.
Then suddenly I got a doubt, as all the examples I have seen for conversion had NFA's initial state with ...
1
vote
1
answer
2k
views
Automata theory: Formal definition of indistinguishable & distinguishable strings and example confusion
In automata theory, we can use Myhill–Nerode theorem to prove that a language is not regular.
The theorem makes use of the concept of distinguishable and non-distinguishable strings.
While it is ...
1
vote
1
answer
115
views
Create a NFA from BNF grammar
How do I create an NFA from BNF grammar?
What I am specifically stuck on is the fact when we have two cases of recursion in the grammar such as in:
< case > ::= < case > < int > 'b' |...
2
votes
0
answers
324
views
Bitap algorithm for Fuzzy search example
I was looking at this work page 31. It is talking about the Wu and Manber 1992 updated Bitap algorithm for Fuzzy search with Non-deterministic Automata. To be more precise this formula:
Let's also ...
1
vote
1
answer
1k
views
DFA- Set of all strings whose 10th symbol from the right end is 1
Problem is "Constructing a Dfa accepting set of all strings whose 10th symbol from the right end is 1 over {0,1}"
The NFA is easy
(0+1)*1(0+1)^9
, but DFA has to have minimum 2^10 states.
...
0
votes
1
answer
393
views
NFA or DFA accepting # of positions of 4k between 0's
Left is the given solution, but it fails for 01110(shouldn't be true) and 010000 (should be true). If we do it like the right one like I did, then there might not be 1 in it so it fails because 000000 ...
0
votes
0
answers
28
views
unable to display tables and diagrams in python for non deterministic finite automata
I want to ask for help to solve this problem, I wonder if there is something wrong with my code or are there tools or extensions that I haven't installed
enter image description here
I've tried to ...
-2
votes
1
answer
48
views
By writing a regular expression or a grammar, describe the language accepted by the NFA
NFA diagram
the strings accepted are aaaaa which is pretty clear. The L = (111 + 1111)* is what I am getting but I need it in regular expression or grammar
1
vote
1
answer
75
views
Why is the most constraint language for this not Regular and instead, Context-Free?
This is the question:
Q: Given the following production rules, which is finite or otherwise the most constrained language in the Chomsky language hierarchy corresponding to the language described by ...