598 questions
1
vote
0
answers
47
views
Question regarding branch and bound algorithm for finding critical DFA's [closed]
I was reading this paper(page 5 and 6) which finds critical dfa's (dfa's with shortest synchronising word with length exactly exactly equal to (n-1)^2) for n <= 7.
https://arxiv.org/pdf/1801.10436
...
1
vote
1
answer
75
views
Testing a matrix to see if it is unitary or Hermitian
I'm using this:
(ma:ident(3),ma[1,1]:%i/2,ma[1,3]:sqrt(3)/2,ma[3,1]:sqrt(3)/2,ma[3,3]:-%i/2,ma);
It gives a 3x3 matrix which I expect to be unitary.
But when trying to test it by using is(ma,(unitary)...
- 119
0
votes
1
answer
191
views
How can I design a Turing machine that recognizes the language { $aⁿbᵐ: m ≥ 2n }?
There are many examples of how to do anbm: m>=0 but not this.
Right now I get that for every a there must be at least two b's marked off on the tape. What is stumping me even more is that m is ...
- 1
-3
votes
1
answer
2k
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
1
vote
1
answer
193
views
Regex to DFA question, don't understand why it is this way
I've been dealing with problem 10 on Leetcode (Regular expression matching), where you are supposed to write a program that matches strings to a given regex.I wrote a solution in C that had passed 308 ...
- 29
-3
votes
1
answer
155
views
Are my DFA's correct? (arbitrary long sequence of 0's and 1's) [closed]
For my exercise I'm supposed to create two DFA's.
The task specifically is:
Construct a DFA over the alphabet Σ={1,0} accepting the following regular languages.
a) An arbitrary long sequence of zeros ...
- 11
0
votes
1
answer
434
views
Create a DFA that contains "11" or ends with "10"
I'm trying to construct a DFA (binary only) that contains "11" or ends with "10".
I tried to do the following:
$q2$ and $q3$ are accepting states
State
0
1
$q0$
$q0$
$q1$
$q1$
$q3$
...
0
votes
1
answer
153
views
Correct finite automata diagrams for these simple problems?
Hello I am learnign about finite automata and I want to see if these diagrams and my explanation make sense.
{w ∈ Σ∗ | w contains the substring 1010} using five states
There is the substring of 1010 ...
- 55
0
votes
0
answers
73
views
Is the concatenation of these two FAs possible in a reasonable length?
I'm trying to concatenate the FAs for even-even and the language of words that contains at least one double a (aa).
The transition table for the concatenation seems to be getting very long. I've ...
2
votes
1
answer
1k
views
Regular expression for L = {w|w doesn't contain the substring 110} over the alphabet Σ = {0,1}
Consider the language L = {w|w doesn't contain the substring 110} over the alphabet Σ = {0,1}
Write the regular expression
Currently I have the regular expression as 0*(10*10)*1*
But the autograder ...
- 43
0
votes
1
answer
515
views
Find a finite automata that for the language L={0,1,2} | needs to include 1002 1,2 are odd and 0 is even
Find a finite automata that for the language L={0,1,2}
with the following criteria:
The word must contain "1002".
The number of occurrences of 1 must be odd
The number of occurrences of 2 ...
- 39
1
vote
1
answer
223
views
a challenging finite automata - what is the language?
I have this finite automata (FA) and want to write its language. I think its
L={x E {0,1} | {x with subset of 00 and ends in 1} and it would help to know what the type of FA it is.
I think it's a DFA ...
- 55
2
votes
2
answers
219
views
Correct labeling for this regular language?
So I am a newbie computer science person and would like some help from the community in helping me understand this subject.
I have this regular language I am trying to determine is 3 things from this ...
- 55
0
votes
1
answer
205
views
Unable to create an DPDA that accepts strings in binary notation multiples of 3
Just learned about DPDA's on my Theory of computation class. Professor gave us a semester task to create a deterministic pushdown automaton state diagram that is able to accept all strings multiples ...
0
votes
1
answer
589
views
Need a DFA for the alphabets {a,b} such that the language must contain equal and even numbers of a and b
The DFA for even numbers of and b is this DFA for even numbers of a and b but the DFA of even and equal number of a and b is not available
L={\epsilon,aabb,abab,baba,bbaa,aaaabbbb,aabbaabb,bbaabbaa,...
- 1