Skip to main content
Filter by
Sorted by
Tagged with
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 ...
adlibbinbitch's user avatar
-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 ...
Auxelia's user avatar
  • 11
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$ $...
Salty Champ's user avatar
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 ...
cool cat's user avatar
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 ...
cool cat's user avatar
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 ...
cool cat's user avatar
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 ...
MUHAMMAD AWAIS's user avatar
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 ...
Anantha Krishnan's user avatar
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 ...
DaneShuler's user avatar
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 ...
asaf meizner's user avatar
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 ...
cool cat's user avatar
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 ...
cool cat's user avatar
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 ...
Santiago Lemus Vallejo's user avatar
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,...
SOURAV's user avatar
  • 1
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 ...
Muhammad Hamad's user avatar
-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 ...
Cyberpunk2020's user avatar
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 ...
Pepe Coco's user avatar
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 ...
Kush_Uttam's user avatar
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 ...
Anantha Krishnan's user avatar
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 ...
comp_sci_noob's user avatar
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 ...
mcYuzu's user avatar
  • 17
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 ...
mindoverflow's user avatar
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 ...
mark's user avatar
  • 81
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.
Duy Duy's user avatar
  • 581
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 ...
Yonathan's user avatar
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 ...
Anubhav Tyagi's user avatar
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 ...
ali_m's user avatar
  • 21
-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?
Marnie's user avatar
  • 21
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 + ...
RipLearning's user avatar
-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 ...
Digvi_sp's user avatar
-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 ...
David542's user avatar
  • 109k
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 ...
Pargins's user avatar
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.
Aditya Johorey's user avatar
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 ...
MehmetG's user avatar
  • 19
-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 ...
Apriana's user avatar
-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, ...
user19187727's user avatar
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).
NyN's user avatar
  • 1
-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 ...
nTn's user avatar
  • 13
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 '...
BrandonStudio's user avatar
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 ...
sandbuzzard's user avatar
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 ...
Tryer outer's user avatar
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 ...
Tryer outer's user avatar
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. ...
Sourav Kannantha B's user avatar
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 ...
HANAN MOHAMMED's user avatar
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 ...
Shivam Chauhan's user avatar
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 ...
dullyourmind's user avatar
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 ...
Pratik Hadawale's user avatar
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 ...
Varscott128's user avatar
-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 ...
explorer's user avatar
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 ...
Priyansh Srivastava's user avatar

1
2 3 4 5
12