Questions tagged [finite-automata]
Questions about finite automata, an elementary automaton model with finite memory. It is equivalent to regular languages and the basis for many more complex models.
1,194
questions
0
votes
1answer
18 views
Can nfa consume more than one letter at a time
If I have a NFA/DFA and I expect inputs of 00, 01, 10, 11 can I read input in groups of 2 binary digits at a time.
like the example shown
0
votes
1answer
22 views
NFA/DFA for $ L= \{a^n b^n a | n\ge0\}$
I have made two DFA’s for $ L= \{a^n b^n a | n\ge0\}$.
First one has several states. The second one is accepting an empty string also.
Somebody please guide me the correct one.
Zulfi.
0
votes
2answers
12 views
Regular expression containing lambda
What is the meaning of lambda here:
$$(b+c)^*(a+\lambda)(b+c)^*(a+\lambda)(b+c)^*(a+\lambda)(b+c)^*$$.
I know that lambda is used in the context of NFA?
Let's suppose we break down the expression ...
0
votes
0answers
21 views
Intersection of two DFA's
I am trying to understand the intersection of 2 DFA's. I got the following link:
Intersection of 2 DFAs
I can't understand why they have not used the symbol 'b'. In the DFA's they have symbol 'b' also ...
0
votes
0answers
17 views
How to implement program with better state machines performance? [closed]
Could I get best performance than I already obtain with automata using better than state machines performance in a common case?
0
votes
0answers
21 views
What exactly is “pattern matching”?
I know some examples of "pattern matching". E.g. in the context of functional programming, and regular expressions.
But is there a precise definition?
In particular, it seems that it has to do with ...
1
vote
1answer
44 views
Meaning of $a\lor b \to b' \lor c'$
So I have done part a) but I have no clue what I am supposed to do for part b), I have been trying for days to wrap my head around and even asked my fellow course mates, none of which seem to know ...
0
votes
0answers
21 views
Use ML to create a graph
I'm currently looking for literature/papers on machine learning techniques to create structures.
In detail, I want to generate finite automata (NFA, DFA), which are useful for student-exercises. So I ...
0
votes
1answer
40 views
Determine if an NFA accepts infinite language in polynomial time
Question Statement: Given a NFA $N$, design an algorithm that runs in polynomial time such that it determines if $L(N)$ is infinite.
(Note that converting NFA to DFA is exponential time).
For any DFA,...
-1
votes
0answers
14 views
construct transition table from equivalence of dfa-minimization
I'm trying to minimize a DFA.
From the state transition diagram, I have formed the table:
And the 0-equivalence is : {q0,q1,q3,q4,q5,q6,q7},{q2}
And 2-equivalence is {q0,q4},{q6},{q1,q7},{q3,q5},{...
0
votes
0answers
27 views
Why does this finite state machine state transition diagram solution has more states than my solution?
I can't figure out what is wrong with my solution and why does it differ from book's solution. I think the only thing that matters is the previous state of A so that there should be two states, one ...
0
votes
0answers
20 views
Possible number of DFAs, NFAs, DPDAs, NPDAs, NDTMs and DTMs for various input parameters
I came across problem asking for possilble number of DFAs for a given number of states and alphabet. I started guessing if we can find possible number different automatas for given number of states, ...
0
votes
1answer
37 views
No nonfinal states in NFA
I know that if there are no non-final states in DFA then the language accepted is $\Sigma^*$.
What will happen if there are no non-final states in an NFA? Can we say it also accepts $\Sigma^*$? Can ...
1
vote
2answers
42 views
Pumping Lemma with Prime Number [closed]
$\text {Could someone please help me with this proof: }$
$L:=\left\{a^{n} d^{m} b^{k} | n, m, k \in \mathbb{N} \wedge m \text { is a prime number}\right\}$
$\text {Maybe we can say, that } w=a^{n}d^{...
-1
votes
0answers
9 views
Build a DFA that accepts strings over {0,1,2} that are divided by 3 and doesn't include the substring 012
Ive tried to draw it but im not finding the right way.
Ive also read it "How to prove a language is regular?" and here - https://math.stackexchange.com/questions/1556655/build-a-dfa-that-accepts-...
-1
votes
0answers
16 views
Help in converting NFA to regular expression [duplicate]
Hi I don't understand how to convert NFA to regular expression in the question below. Can someone help me to solve and understand example below
0
votes
1answer
23 views
Closure of regular languages under “inverse second half”
Theorem. Show that if $L$ is regular, then so is
$$
\varphi(L)=\left\{w \in \Sigma^{*} \mid \text {there exists an } \alpha \in \Sigma^{*} \text { with }|\alpha|=|w| \text { and } \alpha w \in L\...
0
votes
0answers
22 views
Minimal DFA for “$n$th character from the right is $a$” [duplicate]
I am given the following regular expression, which accepts all strings over $\{a,b,c\}$ whose $n$th character from the right is $a$:
$$ (a|b|c)^*a(a|b|c)^{n-1}. $$
The exercise asks for the number ...
2
votes
1answer
48 views
Regular expression for language that does not accept x string (3 letters, |x|=3)
The language I am interested in is $L=\{w∈\{a,b,c\}^*| w$ contains "$bac$" but not "$cab$"$\}$. I am thinking that the result will have the form $L=X_1X_2X_3$, where $X_1=\{w∈\{a,b,c\}^*| w$ does not ...
1
vote
1answer
62 views
Can a dfa return only the final state?
I am given an assignment to design a tiny arithmetic unit (from 0 to 15 inclusive) start with 0 and using a DFA. The operations are as follow:
increment x+1 and if x+1 is larger than 15 then x+1 ...
1
vote
1answer
42 views
What kind of language does the following DFA accept?
can anyone please describe the language this FA accepts? thank you
2
votes
1answer
38 views
Does this argument prove CFLs are not closed under union?
Context free languages are not closed under complementation. This follows from their property of non-closure under intersection:
If CFLs were closed under complementation, then they must have also ...
2
votes
2answers
104 views
Prove that the following language is not regular: $\{0^i1^j : i \neq j\}$ [duplicate]
I was trying to approach this proof, after multiple reads and attempts I am getting nowhere. If someone could help me out that would be great. Should I use the pumping lemma, if so how show I start, ...
0
votes
0answers
28 views
Backwards and forwards automata languages compared with regular languages
Is every language accepted by a BAFDA regular? I am not even sure what the answer is. I tried thinking around canonical examples of non-regular languages (like $0^n1^n$ or $\{ww | w \in \{0,1\}^{*}\}$ ...
2
votes
0answers
19 views
Why are VFSMs not more commonly used?
For a job several years ago I worked with a team using technologies built around Virtual Finite State Machine models for system fault analysis and remediation. Since then, I've found it to be a ...
1
vote
1answer
19 views
Are number of states in a NFA same as Pumping length?
So i was reading a post on Minimum pumping length of regular language where Yuval Filmus has proved that a pumping lemma might have lesser number of states than a minimal DFA. But What about NFA's? ...
4
votes
2answers
60 views
Finding the number of distinct strings in regular expression
Given the regular expression $(1 + \varepsilon + 0 )(1 + \varepsilon + 0 )(1 + \varepsilon + 0 )(1 + \varepsilon + 0 )$, how many distinct strings are in the language? How do you determine this from ...
22
votes
6answers
11k views
Why is English not a regular language?
Surely any language with a finite longest word can be made regular by having an automaton with paths to 26 states for all letters and then having each of those states go to another 26 states, etc., ...
2
votes
1answer
27 views
totally ordered semigroups
Given a semigroup is it possible to give a total order to it?
If not possible in the general case then what about the case of finitely generated finite semigroups?
Does there exist a natural ...
0
votes
0answers
26 views
Finite state machine for a modified traffic controller
Consider a traffic light controller for an intersection of a main street and a smaller street. Both streets are one-way streets. The intersection has two traffic lights, one for each street. In normal ...
0
votes
0answers
24 views
How to deal with sets in NFA?
I have a transition system that I'm converting to an NFA. In the TS, I have a trace of {b} {a, b} {a, b, c}. How would I handle these sets in the NFA? In other words, what would be the path to follow ...
3
votes
1answer
112 views
How do I solve these questions regarding homomorphism?
Questions:
Give an example of a homomorphism, using the same alphabet, Σ, for both languages A and B.
Now, give a second example of a homomorphism but this time using two different alphabets, Σ and ...
0
votes
1answer
91 views
Prove $\epsilon(S\cap T)\subseteq S \cap T$
Suppose there are sets $S\subseteq Q, T\subseteq Q$ such that $T=\epsilon (T),S=\epsilon (S)$.
Prove $\epsilon(S\cap T)\subseteq S \cap T$
Definition of $\epsilon$- closure for epsilon NFA is:
...
0
votes
1answer
59 views
NFA for all strings not containing 1010
if I want to design a NFA (that's NOT A DFA) that accepts the set of all strings that do not contain the substring 1010, is this correct? because I can just accept 1010 by capturing it in the starting ...
-1
votes
1answer
46 views
Constructing a DFA of strings that are in A but not in B
I am tasked with creating a DFA for the regular language L = A/B, which are the strings that are in A but not in B. The alphabet is Σ = {a,b,c}
I am not really sure where to even start with this one, ...
1
vote
1answer
199 views
Let M be an $\epsilon$-NFA and let $S\subseteq Q$. Prove $\epsilon (S) = \epsilon (\epsilon (S))$
Let M be an $\epsilon$-NFA and let $S\subseteq Q$. Prove $\epsilon (S)= \epsilon (\epsilon (S))$.
I would like to prove this by contradiction but I don't know if my idea is correct.
Definition of $...
0
votes
1answer
55 views
DFA for language of all strings avoiding 'aa'
I'm trying to draw a dfa for this description
The set of strings over {a, b, c} that do not contain the substring aa,
current issue i'm facing is how many states to start with, any help how to ...
1
vote
1answer
80 views
What will be the pictorial diagram of this transition table?
I was doing my homework and I am confused on what I'm doing, it can't be that straightforward. I'm making a mistake somewhere. I tried looking for practice problems but they don't cover my issue ...
0
votes
0answers
29 views
Proving a language is Not Regular without using Pumping Lemma? [duplicate]
I was wondering how one would go about proving a language is Not Regular without using the traditional pumping lemma contradiction.
$$L = \{ 1^k 0^n 1^n 0^k \mid k \geq 0, n \geq 0\}$$
I've seen a ...
1
vote
3answers
82 views
All languages are regular, as unions of singleton languages
We know that singleton languages (languages containing exactly one word) are regular. We also know that a finite union of regular languages is also regular.
Suppose there is a non-regular language $L$...
1
vote
1answer
36 views
Finite / Infinite Languages True/False and why?
Just doing some work on Finite and infinite languages. And came across some statements I know the answer to but not sure how to explain why.
There are finitely many finite languages.
-This is false ...
0
votes
0answers
36 views
How to prove that L(G) is not regular by contradicting the pumping lemma?
I am trying to prove that this language is not regular by contradicting the pumping lemma. I have been reading and looking at examples but all the examples I have seen is in the for of a REGEX. I am ...
2
votes
1answer
31 views
If DFA has two states, which of the conditions hold?
Let $L$ be a regular language ,and $M = (Q, Σ, δ, q_0, A)$ is a DFA such that $L(M) = L$.
Prove that if $|Q| = 2$ then one of the following holds :
a) $L=∅$ b) $ε∈L$ c) $∃a∈Σ$ and $a∈L$
The problem ...
1
vote
1answer
61 views
Proving a DFA recognizes a language using induction
The following DFA recognizes the language containing either the substring $101$ or $010$. I need to prove this by using induction.
So far, I have managed to split each state up was follows:
q0: ...
2
votes
1answer
126 views
Method to construct a finite state machine for a finite-size language L
I need to define a method to construct a finite automata for a finite language L (part of my proof for something else).
My idea:
Create $|L|$ accepting states.
For each input string $s$ from $L$, ...
3
votes
1answer
100 views
Is Palindrome subset of a regular language regular?
Suppose we have $L$ being a regular language with alphabet $\Sigma$, if we define $M=\{ x \in \Sigma^{*} \mid xx^{R} \in L \}$, then we know that $M$ contains all half copies of palindrome strings ...
0
votes
2answers
47 views
No FSM/Regex exists for this language right?
The language is this:
$L = \{w \in \{a,b\}*:$ each $a$ has a matching $b$ somewhere in $w$ $\}$
This wouldn't have an FSM since you'd need infinite states of depth for each unmatched a you have, ...
2
votes
0answers
28 views
Minimal regular expression from minimal NFA for finite language in polynomial time?
Given a minimal NFA for a finite language, is there a polynomial-time algorithm to find a minimal regular expression for the same language?
This question is based on a recent question regarding ...
2
votes
1answer
36 views
General algorithm to find a minimal branching program
Given a general branching program, is there an algorithm which can find an equivalent branching program $P$ of minimal length. That is $|P| \leq |P'|$ for all equivalent branching program $P'$.
If ...
-1
votes
1answer
97 views
How to generate Deterministic finite automaton for given language
Problem: Write a program which generates Deterministic finite automaton which accepts given language. Language is defined with alphabet and start/end sub strings.
For example: Alphabet={a,b,c}; start ...
