Skip to main content

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
0 answers
73 views

How to work thompson's construction algorithm?

Could someone explain to me, through an example, how the McNaughton–Yamada–Thompson algorithm works in a way that I can understand? Thank you in advance for your helpful response!
ProgrammerGnome's user avatar
-1 votes
1 answer
43 views

Is this correct Context free grammar(CFG) for these two languages?

Question 1: L = { 0^n 1^n | n > 0 } My answer = S -> 0 S 1 | 10 Question 2: L = { 101^n0^2n | n > 0 } My answer = S -> 101 S 00 | 100 Can anyone correct this if there is any issue with ...
Elijah's user avatar
  • 1
1 vote
0 answers
29 views

In regular language inference, how is the observation table kept consistent?

I am trying to understand the background literature on regular language inference in the TTT paper ("The TTT Algorithm: A Redundancy-Free Approach to Active Automata Learning" by Isberner, ...
Rahul Gopinath's user avatar
1 vote
1 answer
121 views

How to construct complement of NFA universality?

Given an input NFA, can one construct an NFA that is universal (that is, accepts all its inputs) if and only if, the input NFA isn't universal? I tried to use the fact that NFA-universality is PSPACE-...
NooneAtAll3's user avatar
2 votes
1 answer
102 views

Applications of ω-automaton in engineering

Finite automaton is a well-known topic which finds applications in software engineering (e.g. pattern matching or regular expressions in general). ω-automaton are another kind of automaton, defined ...
Weier's user avatar
  • 231
0 votes
1 answer
59 views

Determining the language of a DFA

I've tried quite a large amount of examples, starting from 1 bit all the way up to 5 bits yet I couldn't put my finger on any recurring pattern of words that are accepted. the DFA is as such: The ...
Aishgadol's user avatar
  • 355
1 vote
1 answer
254 views

How to build a deterministic or non deterministic finite automat for a language

$L_1$ and $L_2$ are two languages that have a finite deterministic automaton. $Σ = \{0,1\}$ for the two languages. Let $L=\{x∈L_1\mid \text{there exists } y∈L_2,\text{such that } \#_0(x)=\#_0(y)\}$, ...
ella's user avatar
  • 11
0 votes
1 answer
64 views

Proving that the intersection of two languages is regular or not?

Let $B$ and $C$ be two languages on $A = \{a,b\}$: $B = \{ w \mid w \text{ has the same number of }a\text{ and }b\text{ symbols}\}$ $C = \{ a^n b^m \mid n,m \ge 0\}$ Describe $B \cap C$ and determine ...
Luca 's user avatar
  • 63
0 votes
1 answer
69 views

Intersection of a regular and a non-regular language can give a non-regular language?

Determine two languages L and L1 on the alphabet {a,b} with regular L, L∩L1 is non-regular and L1 does not contain L. I came up with this solution: L = { w | w ends with the string aba} L1 = {w | w = ...
Luca 's user avatar
  • 63
0 votes
2 answers
68 views

Can the intersection of 2 non-regular languages ​be a regular and infinite language?

The outline of the exercise is this: Describe two non-regular L1 and L2 languages on A = {a,b} such that L1∩L2 is infinite and regular. The proposed solution to this exercise is: L1 = {a^n b^n | n >...
Luca 's user avatar
  • 63
0 votes
1 answer
42 views

Proving a language is not regular using Pumping Lemma

So I am given the language qr where q is any combination of a's and b's. r is then the reverse of whatever q is. For example, abba is in the language because we can make a q = ab and r = ba I have to ...
CSStudent's user avatar
1 vote
0 answers
13 views

Is there a symbol in FA/FSM for everything else

I remember in a Computability Theory class building a state machine for an assignment that required many 'go-back' transitions on $\Sigma - symbols$ for all symbols not already handled. This was very ...
davolfman's user avatar
  • 111
0 votes
0 answers
40 views

Can someone explain the following NFA?

I'm learning NFA and the following question is confusing me. Can Someone explain the answer. I have a feeling that it might be wrong. Thank you!
ultranoobcoder's user avatar
-1 votes
2 answers
477 views

Create DFA such that every substring of w of length 3 contains two or three 0's with w={0,1}

I am attempting to draw the DFA of this problem but I'm kind of stuck. In another post I saw that the DFA should have 10 states. I'm finding it hard to even understand the question, is the input to ...
Jellyfish's user avatar
0 votes
0 answers
56 views

1 way 2 stack and 2 way 2 stack Pushdown Accepters that accepts $L=\{a^{(n^2)} \mid n \geq 1\}$

Using a 1 way 2 stack, and a 2 way 2 stack PDA, I want to check if the length of an input string is strictly a perfect square number. How can I do this in both approaches?
user164486's user avatar
0 votes
2 answers
79 views

Why does lexer has O(n) time complexity?

According to my CS knowledge so far, a lexer uses DFA(which takes linear time) for 'each' token type to find the next token, so in the worst case, it should try 'all possible' token types of a ...
Hunee Park's user avatar
0 votes
2 answers
130 views

How to find prefixes and suffixes for infinite languages? (Automata)

L= {abc} prefix = {epsilon,a,ab,abc} suffix = {epsilon,c,bc,abc} It's easy to find suffixes and prefixes for finite Regular languages. But what will be the ...
Vedant Khandelwal's user avatar
0 votes
0 answers
310 views

Turing machine for a^n b^m c^n d^m

The state diagram for the initial part of this turing machine given as: Here, we are basically traversing through the input tape, changing occurence of 'a' to X1, and 'c' to X2. After that we go back ...
Tanuj's user avatar
  • 101
0 votes
0 answers
34 views

What is the minimum length word accepted by the product of these simple loop automata?

Let $A_{n} = (aa|aaa|aaaa|\dots |a^{n-2})(a^{n})^* $ where $n \geq 4$ is some natural,and $A_2 = (a^2)^*, A_3 = (a^3)^*$. Clearly every transition is thus labeled by an $a$. From now on let $A_n$ ...
HighAsAKiteOnMath's user avatar
2 votes
1 answer
121 views

What is the Minimum length of a string that is accepted by a DFA that shows that the language accepted by that DFA is infinite?

What is the minimum length of a string that is accepted by a DFA, shows that the language accepted by that DFA is infinite? I checked this post How to determine if an automata (DFA) accepts an ...
Rajsukh Mohanty's user avatar
0 votes
1 answer
230 views

Construct a regular grammar that produces all possible strings of $\Sigma = \{a,b\}$ that do not contain substring 'abba'

I'm really stuck here and do not know what to do. So far, I've constructed a DFA and a regular expression that produces the aforementioned set of strings. Namely, the DFA looks like: After a lot of ...
Nyquist-er's user avatar
1 vote
1 answer
79 views

DFA for even concatenation of strings from a language

If I have a deterministic finite automaton (DFA) with a language $W$, and I need to create another DFA that returns all the strings that are a concatenation of an even number of strings in $W$, how ...
Catherine H.'s user avatar
0 votes
0 answers
61 views

After converting a CFG to a PDA, what is an example input string to the PDA?

For example, the following CFG: S$\rightarrow$aSb|$\epsilon$ A valid string within the language described by the CFG would be, e.g., "aabb". The converted PDA has the following form: The ...
There's user avatar
  • 111
0 votes
0 answers
49 views

Binary combinatorics with rank

I am looking at finding acceptable binary values with maximum 2 consecutive 1s and 0s, from a range of maximum 6 bits (2^6 values). Also, I want to rank and unrank these subset of values (in ...
Dave's user avatar
  • 25
0 votes
0 answers
47 views

DFA for "K" bit value with max "n" consecutive "0"s and "1"s

I had posted earlier a question regarding ranking max "n" consecutive "0"s and "1"s in a "K"-bit string - Order in a subset I got clarification regarding how ...
Dave's user avatar
  • 25
0 votes
0 answers
279 views

Minimum number of states in a DFA

Consider the language L given by the regular expression (a + b )*b(a + b) over the alphabet {a, b} . The smallest number of states needed in a deterministic finite-state automaton (DFA) accepting L is ...
Rishi's user avatar
  • 1
0 votes
0 answers
65 views

How to convert a NFA to alternating finite automata AFA?

I am trying to construct an AFA from a NFA, how do I know if a state of NFA becoms existential or universal in the AFA?
Lea's user avatar
  • 1
0 votes
1 answer
72 views

Question about remainder in automata construction that checks divisibility

I'm trying to understand de construction of a DFA from the book "Introduction to Automata Theory, Languages, and Computation by John Hopcroft and Jeffrey Ullman 1st ed" It says: Where it ...
PerseP's user avatar
  • 101
4 votes
1 answer
136 views

Is the set of all DFAs countable?

Let $\Sigma$ be a finite nonempty alphabet. Is the set of all DFAs over $\Sigma$ countable? I know the set of all regular languages is countable, however, it is impossible to build an injection from ...
Kantig Shoter's user avatar
0 votes
2 answers
42 views

Linked Finite State Machine

Let us assume, we have a FSM (to be precise, an epsilon-NFA) in which I've got redundant structures. I am looking for a framework that allows to factor out the redundant part into some kind of ...
derM's user avatar
  • 101
4 votes
1 answer
81 views

Translating non-deterministic finite automata with counters to deterministic ones

I know there are algorithms for translating regular NFAs into their corresponding DFAs. Can these algorithms be applied to automata that employ transitions involving counters in a straightforward way, ...
136's user avatar
  • 141
2 votes
1 answer
269 views

How to convert NFA with multiple start states to NFA with single start state without epsilon transition?

I can easily convert NFA with multiple start states to NFA with single start state with epsilon transition. But I want to know how can I do so without epsilon transition Here's my idea Suppose s1 and ...
Archaic's user avatar
  • 21
0 votes
2 answers
384 views

What can i say about L1 given that L2, L1L2 and L2L1 are regular?

I found this question in one of our past exams, and I'm not to sure about the correct answer. I have a language L1 (which i don't know anything about) and another language L2, which is regular, the ...
pezbecoding's user avatar
-4 votes
1 answer
86 views

For each of the following languages, give a regular expression over {a, b}

$\{a^{2n}b^{n+k+1}a^k ∈ \{a, b\}^∗ \mid n \ge 0, k \ge 0\}$
user162351's user avatar
0 votes
3 answers
115 views

How to create a DFA with memory

How can I create a DFA that has memory such that I could write a rule for this DFA that states ...
MlLearner's user avatar
0 votes
1 answer
108 views

What strings are accepted by the described DFA?

Could someone clarify what strings are accepted by the described DFA? Draw a DFA for the set of all strings with two consecutive 0’s followed by two consecutive 1’s over Ʃ= {0,1}
Saiful's user avatar
  • 1
1 vote
1 answer
65 views

Does graph traversal require stack machine?

I'm writing a graph traversal function to be used in a garbage collector. To avoid stack overflow, I used a finite state machine. Roughly, it descends into child nodes recursively to mark objects, and ...
DannyNiu's user avatar
  • 352
0 votes
1 answer
484 views

nfa of the Language L={w belongs to (a,b)*/w starts with aa or ends with aa} with or being not exclusive

I have a question I need to give the NFA of the following language: L={w belongs to (a,b)*/w starts with aa or ends with aa} with or being not exclusive meaning I can have a word that starts with aa ...
LK.'s user avatar
  • 1
3 votes
2 answers
44 views

Does there exist terminology to discern NFA states and NFA-transformed-into-DFA state?

I can't find this from surface search in the literature When one observes/simulates NFA after processing several characters, one has to consider both "internal states of NFA" (individual ...
NooneAtAll3's user avatar
1 vote
1 answer
21 views

Meaning/veracity of "each state has [..] or two outgoing ϵ transitions" in Thompson's construction

The dragon book lists properties of an NFA N(r) created using Thompson's construction, in particular: Each state of N(r) other than the accepting state has either one outgoing transition on a symbol ...
Evgeniy Berezovsky's user avatar
1 vote
0 answers
88 views

Regex to DFA - How do I implement parsing preferences in regex search?

I've tried a to implement a Regex to DFA converter, and it works, so far, but I don't understand how to implement "parsing preferences" in the DFA. A classic example is $a^*$. This regex is ...
Jan Schultke's user avatar
0 votes
0 answers
329 views

Real-life applications of pure Mealy machines

I'm currently studying formal methods in software engineering related to state machines, specifically Mealy machines. This made me wonder how relevant Mealy machines really are for practical ...
programonkey's user avatar
2 votes
1 answer
94 views

Finite State Machine without recursion

I have found utility in state machines that do not have the complexity of recursion: no self or ancestral transitions. Is there a name for this sub-category of FSMs? Are they commonly used or ...
Synesso's user avatar
  • 123
0 votes
0 answers
24 views

Theory of computation

I am trying to look answer for this question of toc please help me find the answer. The question is : Construct epsilon NFA(Non deterministic finite automata) for regular expression (0+1)*1(0+1)
Amy's user avatar
  • 1
5 votes
2 answers
414 views

Creating a deterministic finite automaton for strings of 2k ones and 3q zeros or a general language

I was requested to draw the graph of a finite state machine whose language is $$L = \{ w \in \{0, 1\}: w \text{ has $2k$ ones and $3q$ zeros }\}$$ In other words, the number of ones must be even and ...
lafinur's user avatar
  • 195
1 vote
1 answer
40 views

Counting States in the trim automaton for $\cup_{i=1}^{p} L_i \circ L'_i$

Preliminaries. Let $n,m,i,j,p,c \in \mathbb{N}$ with $n,m,i,j,p,c \geq 1$. Let our alphabet be $\{0,1\}$, with non-empty languages $ L_i \subseteq \Sigma^n$ and $ L'_i \subseteq \Sigma^m$. The other ...
ShyPerson's user avatar
  • 925
2 votes
1 answer
228 views

ALL_{NFA} is PSPACE-complete

Show that $ALL_{NFA}$ = {$\langle M\rangle : M$ is $NFA$ and $L(M) = \Sigma^*$} is $\text{PSPACE-complete}$. I've manged to prove that the langauge is in $\text{PSPACE}$. Indeed, it is easy to see ...
GeoArt's user avatar
  • 21
2 votes
1 answer
148 views

Does my finite state automaton accept a string iff it contains the given string as a substring?

I am trying to write down the generalized form of the finite automata which accept strings which contain as a substring an arbitrary string. Here is what I have come up with — I was hoping someone ...
ZarakshR's user avatar
  • 125
0 votes
1 answer
35 views

Counting States in the trim automaton for $(L_1 \cup L_2 \cup \ldots \cup L_p) \circ L'$

Preliminaries. Let $n,m,p \in \mathbb{N}$ with $n,m,p > 1$. We allow that $p$ could be large but still bounded by a function of $n$: $p = O(2^n)$. Let our alphabet be $\Sigma = \{0,1\}$, with non-...
ShyPerson's user avatar
  • 925
2 votes
2 answers
91 views

Counting States in the trim automaton for $L\circ L'$

Preliminaries. Let $n,m \in \mathbb{N}$. Let our alphabet be $\Sigma = \{0,1\}$, with non-empty languages $ L \subseteq \Sigma^n$ and $ L' \subseteq \Sigma^m$. We follow the standard definition for ...
ShyPerson's user avatar
  • 925

1
2
3 4 5
36