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.

Filter by
Sorted by
Tagged with
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
24 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
22 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
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
1
vote
1answer
28 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
106 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
201 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
127 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
98 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 ...
0
votes
0answers
74 views

If $L$ is a regular language then so is $L/a =\{w | wa ∈ L\}$, where $L$ is a language over $\Sigma$ and $a \in \Sigma$

I'm trying to work out a proof by construction that $L/a$ would be regular. $a$ is any final symbol at the end of an accepted string, so I figured the only part of the machine that would have to be ...