598
questions
1
vote
1
answer
48
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 ...
-3
votes
1
answer
54
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 ...
0
votes
1
answer
121
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$
$...
0
votes
1
answer
43
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 ...
0
votes
0
answers
18
views
A simple push down automata for empty set
Suppose we have an empty set in finite automata. We know its context-free grammar is S - S.
Is the push down automata simply:
Given that a empty set cannot have an:
input state as it recognizes no ...
0
votes
0
answers
24
views
On the right path? Finite automaton diagram for a regular language
Hello, I am trying to show that a language L is regular through a regular expression and a finite automaton.
The expression makes sense, but wanted to see if I am on the right path for the finite ...
0
votes
0
answers
33
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 ...
0
votes
0
answers
33
views
Correct implementation of GMM-HMM for Speech Recognition
For N words, we have N HMMs. In each of the HMMs, the states are the GMMs. Each GMM models unique phoneme (with or without belonging to a particular context). It is these HMMs (words) that constitute ...
2
votes
1
answer
371
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 ...
0
votes
1
answer
210
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 ...
1
vote
1
answer
96
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 ...
2
votes
2
answers
80
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 ...
0
votes
1
answer
93
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
222
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
vote
1
answer
89
views
Convert the given Moore Machine into Mealy machine
Convert the given Moore Machine into Mealy machine
I'm currently working on converting a Moore Machine into a Mealy machine, and I'm uncertain about the correctness of my solution. I would greatly ...
-2
votes
1
answer
31
views
What is the flaw in the proof of the countability of the set of finite language?
Let FT be the class of all finite languages over {0,1}.
Suppose FL is countable, so we can enumerate all members of FL as
FL = {L_0, L_1, L_2, ...}
Meanwhile, we also enumerate all strings over the ...
0
votes
1
answer
47
views
NFA or e-NFA for the condition , n % 5 = 0 where n is the number of 1s
How to create an NFA or eNFA that satisfies the condition
n mod 5 = 0 where n is the number of 1s
I made two NFAs and I am not sure if they are correct. I am confused if how many states should be ...
0
votes
1
answer
774
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
0
answers
17
views
On the use of subsequential symbol $ in Finite state transducers to pad out the context, for composition
I am going through hbka.pdf (WFST paper - https://cs.nyu.edu/~mohri/pub/hbka.pdf)
I am trying to understand this paragraph. Pg 22/31.
"The deterministic transducer composes without a matching ...
0
votes
1
answer
77
views
Convert Nondeterministic Finite Automata to Regular Expression
I am having a really tough time on this conversion problem. I have read, re-read and watched videos but I am pretty sure the answer I am coming up with is not correct.here is the diagram of the NFA
I ...
0
votes
1
answer
84
views
How do I make a string validator for Deterministic Finite Automata?
The regular expression for the DFA that I need to validate a string with is (bab | bbb) (a* b*) (a* | b*) (ba)* (aba) (bab | aba)* bb (a | b)* (bab | aba) (a | b)*
I thought of using transitions to ...
0
votes
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 ...
0
votes
1
answer
270
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 ...
1
vote
1
answer
104
views
Using bracket for automata
What is the difference between (ab)* and [ab]* when we write in Automata regular expression? In my opinion, they both mean ab zero or more times, but they don't.
0
votes
0
answers
25
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 ...
0
votes
1
answer
297
views
Given a DFA with multiple Final states. How can I find its compliment?
It is not possible to have multiple start state in DFA but how can I achieve Compliment operation on DFA having multiple Final states?
I try Complimenting the language of given DFA but how multiple ...
2
votes
1
answer
90
views
Complement of a given Language for a DFA
For DFA, the alphabet Σ = {a,b} the language this DFA will recognise is {w|w must contain a}. For this language that the DFA recognises, what would be the compliment of this language or how would it ...
-1
votes
1
answer
74
views
Representing regular expressions with DFA state diagrams
I have these regular expressions:
a) 0(10)*
b) a(b+c+d)
c) b*(aa*b*+ε)
I created these state diagrams for them:
Are they correct?
0
votes
1
answer
85
views
Can this language be expressed with a regular expression?
The given language is:
B = { aibic2m | i ≥ 0, m ≥ 0 } ∪ { arbsc2t | r ≥ 4, s ≥ 4, t ≥ 0}
My Prof has provided a regular expression for this language which is:
a4a* b4b* (c2)* + (epsilon + ab + a2b2 + ...
-1
votes
1
answer
581
views
Is it possible to have more than one minimal DFA 's for a regular language?
If we create two DFA's for a language L say DFA A and DFA B. Then, after minimising the DFA's we get their corresponding equivalent minimal DFA's . Is It always the case that both minimal DFA's have ...
-1
votes
1
answer
268
views
Writing the production rules of this finite state machine
Consider the following state diagram which accepts the alphabet {0,1} and accepts if the input string has two consecutive 0's or 1's:
01001 --> Accept
101 --> Reject
How would I write the ...
0
votes
1
answer
252
views
Finite State Automata (FSA): Repeated output problem
I'm constructing a FSA that print sheep ("baa...!") or cow ("moo...!") in which only even number of vowels are accepted. My FSA is as the following but I don't know why the ...
1
vote
1
answer
64
views
what is the meaning of {} in the regular expressions {a + ab}*
I wonder what is the meaning of curly brackets{} in the regular expressions {a + ab}* and how are they different from the round brackets() in regular expressions.
1
vote
0
answers
65
views
How i can use DFS with a final state automata in Prolog?
I have a final state automata and i want to see all the patterns. This automata is about morphology of Turkish.
Turkish is an agglutinative language. I analyze words and and find their morphemes and ...
-2
votes
1
answer
519
views
Regular Expression | Automata Theory
does anyone know about regular expressions of the following languages:
the set of all strings starting with 000 and not ending 11
the set of all strings with odd string length and ending in 111
L6 is ...
-1
votes
1
answer
144
views
Why doesn't {a^nb^n | n >= 0} follow regular language closure properties?
Using the pumping lemma, we can prove that {a^nb^n | n >= 0}, but what is not clear is the following.
{a^n | n >= 0} is regular by itself and so is {b^n | n >= 0}, and if I am not mistaken, ...
0
votes
0
answers
78
views
Construct a minimal DFA
Construct a DFA for the set of string over {a, b} such that when length of the substring "aba" is divided by 3 leaves remainder 2 i.e, |w|aba = 2(mod 3).
-1
votes
1
answer
93
views
L={aʲbᵏaˡ | l = j * k} Context free? Recursive?
I have to classify the language L={aˆjbˆkaˆl | l = j * k}.
I applied the pumping lemma for CFL and think that it is not context free. However, to prove that it is in fact recursive or recursively ...
0
votes
0
answers
121
views
How to make a FA from regular expression with span match?
I want to make a finite automation or finite state machine from a regular expression. The FA should shift when received a specific character. For example, state A would shift to state B when received '...
1
vote
0
answers
53
views
How this state set of DFA was retrieved from the given NFA
I have this NFA:
1,{2, 3}
2,empty
3,{4}
4,empty
All the arrows in this NFA are epsilon-arrows.
I understand that all possible states that can be reached from each of the states, using only epsilon ...
1
vote
2
answers
635
views
Complement of non-deterministic context-free language
The complement of a context-free language is not always context-free. It is not allowed to just swap the final and non-final states of an NPDA and assume that it produces the complement of the ...
1
vote
1
answer
766
views
Remove first useless productions and then unit productions?
When transforming a Context-free grammar into Chomsky Normal Form, we first remove null-productions, then unit-productions and then useless productions in this exact order.
I understand that removing ...
2
votes
0
answers
92
views
Why text-based regex engines cannot handle lazy quantifiers?
I have came across many times that, text-based regex engines cannot support lazy quantifiers. But I could not find why. But I came to know that, they internally use DFAs, and they do not backtrack.
...
0
votes
2
answers
238
views
The grammar of a language of a NFA state diagram - Antlr v4
I am trying to write the grammer of the following NFA diagram
My code is
grammar LTFA;
rS: 'Start' rA | EOF;
rA: 'Select_coffe' rB;
rB: 'Enter_money' rC | 'Cancel' rS;
rC: 'More_money_needed' rC ...
0
votes
1
answer
721
views
How L={ww^Rx| where w, x belongs to {a,b}^* } is a regular language?
I have understood that L={wxw^r|w,x belongs to {a,b}^* } is regular because it turns out to be the pattern of starting and ending with same symbol but I am not getting the proper explanation that how ...
2
votes
2
answers
4k
views
Design a turing machine to accept {1^n : n is prime number}
Design a Turing Machine to accept {1^n: n is prime number}.
I have this homework to make a recognizer Turing Machine that will be accepted if the occurrences of 1 are equal to any prime number. As of ...
0
votes
1
answer
997
views
When to use Ø for states in DFA / NFA
I am confused about the usage of "Ø" in the DFA / NFA ( Let's talk about this in the context of DFA to NFA conversion )
Let's say that I have a NFA as follows:
enter image description here
...
0
votes
1
answer
258
views
Memory efficient way to store DFA transition table with large alphabet?
I am trying to implement a very simple state transition table for a DFA, but I'm running into some efficiency problems.
If I arrange a transition table with each row as the source state, each column ...
-2
votes
2
answers
145
views
Deterministic finite automata uses
I know how a dfa works but the only thing I'm confused is about it's use.
I've seen it's several applications on the internet like it is used in Traffic lights, in parser etc. but what is the exact ...
0
votes
3
answers
3k
views
why a^m b^n where m,n > 0 is a regular language but a^n b^n where n > 0 is non regular language
a^m b^n where m,n >= 0 is a regular language but why a^n b^n where n >= 0 is a non-regular language?
In both languages, we are taking an infinite number of a's and b's but why we could build a ...