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
1
vote
0answers
46 views

How design a Deterministic finite automata which accept string starting with 101 and how to draw transition table for it if there is a dead state

I’m trying to design a DFA which accept string starting with 101 if the string start with 0 then it goes to dead state.Is my design is correct or wrong? And I don’t know how to draw transition table ...
1
vote
0answers
34 views

k-limited solution for PCP

So there's following problem, that has been bugging me for the last few days: A solution of a PCP $ i_{1},\dots,i_{n}$ with the cards $(x_{1} ,y_{1}),\dots,(x_{m}, y_{m})$ is considered as $k$-...
1
vote
2answers
32 views

Computing automaton for $L(A) / L(B)$ gives ones for $A,B$

I'm trying to figure out whether infinite language change the answer. Show that the following language is decidable: $$L=\{\langle A,B \rangle : \text{$A,B$ are DFAs, $L(B)$ is finite, and $L(A)/ L(B)...
0
votes
0answers
25 views

I can't seem to convert a NFA to a regex. What am I doing wrong? [duplicate]

I have the following diagram : I try to remove state 3: Now I do this: What do I do now to get my regular expression? I'm stuck.
0
votes
2answers
29 views

In general, how does a DFA know how to successfully process a string the intended way?

Suppose we have: $$A\text{ }\colon=\{x, y, z\}$$ $$M\text{ }\colon=\text{some DFA using A}$$ $$S\text{ }\colon=xyzxyzxyz$$ Intuitively, one might say $S$ is fed to $M$ on a per-character basis. This ...
2
votes
2answers
60 views

Prove that every regular subset of $a^nb^n$ is finite

How to prove that every regular subset of $L=\{a^nb^n \mid n\ge0 \}$ is finite? I know that every finite language is regular, and it's not true that every regular language is finite. I also know that $...
1
vote
1answer
23 views

When can a Non-Deterministic Finite Automaton with Epsilon transitions considered to be in an accepted state?

A non-deterministic finite automaton is considered to be halted when either the whole input string has been consumed or when we reach a state where no available transition (if any) matches the current ...
2
votes
0answers
28 views

Regular string relations - proof of correctness

Let $T \subseteq \Sigma^* \times \Sigma^*$ be a regular (rational) relation. We define the obligatory rewrite relation over $T$ as follows: $$ R^{obl}(T) := N(T) \cdot (T \cdot N(T))^* $$ $$ N(T) := ...
0
votes
1answer
28 views

Convert the given NFA to DFA

I am trying to find an DFA for the regular language given by the expression $L\left( aa^{\ast }\left( a+b\right) \right)$. First simplifying $L\left( aa^{\ast }\left( a+b\right) \right)$ we get $L\...
0
votes
0answers
18 views

Mealy machine and moore machine

Can we compute the number of machine of two kind of transducers (mealy and moore) with $n$ states, and lenght of input symbols $m$, and lenght of output symbols $p$.
0
votes
0answers
20 views

About number of NFSTs

Can we proof the number of NFSTs with $n$ states : $n.2^{mpn}.2^{n}$ where $p$ is the cardinal of input alphabet and $m$ the cardinal of output alphabet.
1
vote
1answer
25 views

Is regex with backreference still able to be implemented by finite automata?

I recently learned that regex support backreference which enables referring to a matched group in the pattern itself. E.g. a regex (.)\1{2,} matches two or more ...
1
vote
1answer
23 views

Definiton of a certain symbol in a proof(The right linear languages are exactly the finite state languages)

I want to stress that i am not looking for a proof of this question, but rather if someone(that is familiar with the proof and it's context) can explain to me what the symbol 'e' means in the context. ...
-1
votes
1answer
22 views

How can I prove that the accepted language of a given DFA or NFA or REGEX is equivalent to a given language

I found this How do I verify that a DFA is equivalent to a NFA? but as it states it is not really a good question more of how can I check myself during an exam. Because as you might know to do this by ...
0
votes
1answer
28 views

Is there any property about height of PDA?

I'm trying to find a PDA for $L$ which modifies the stack height at most one. $L=\{a^ib^i\mid i\geq 0\}$ I think there is no such PDA but how can I prove it? My attempt is for a given string, find ...
0
votes
0answers
29 views

Is language bin(n)bin(2^(k+1) n + 1)^R context-free

I have a problem with this exercise. For language $$L_1 = \{ w \in \{0, 1\}^* : \exists k \in \mathbb N \ w = \text{bin}(n)(\text{bin}(2^{k+1}n + 1))^R \},$$ where $\cdot^R$ reverses a string and $\...
3
votes
1answer
70 views

Finding the upper bound of states in Minimal Deterministic Finite Automata

I have a task to determine the upper bound of states in the Minimal Deterministic Finite Automata that recognizes the language: $ L(A_1) \backslash L(A_2) $, where $ A_1 $ is a Deterministic Finite ...
0
votes
0answers
52 views

Does the order of ripping off the states matter?

Do we get same regular expressions at the end regardless of the order that we take the states step by step? Can somebody prove by exemplification?
0
votes
1answer
25 views

How to define an automata for zig zag concatenation? [duplicate]

I have two DFAs one for language A and one for language B. I'm asked to make an FDA that is the zig-zag concatenation of letters of A and letters of B. This is described by the following: {w: w = $a_1 ...
0
votes
2answers
17 views

Regular languages, automata

I want to ask about the definition of regular languages. My book says there has to exist a deterministic finite automaton that recognizes it. Does this mean the finite automaton recognizes exactly ...
1
vote
1answer
91 views

Zigzag concatenation of two languages

Given two regular languages $A,B$ on the same alphabet $\Sigma$, I want to show that the following language is regular: $$ \{a_1b_1 \ldots a_kb_k \in \Sigma^* \mid a_1,\ldots,a_k,b_1,\ldots,b_k \in \...
-1
votes
1answer
32 views

Proof for palindrome grammar by induction

I can't seem to find a solution to the following question. Given the following grammar for palindromes: $$G_{pal}=\{\{a,\dots,z\},\{P\},P,R\},$$ with $R$ consisting of the rules ...
0
votes
2answers
22 views

NFA that ends with 0 and doesn't have 11 after the first 0

So as the title says i m trying to find this NFA. So far i thought to make an NFA that "guesses" what comes after the first 0 and i got this: After some time trying to get rid of all the extra (7 !)...
3
votes
1answer
117 views

Why is this language a regular language?

Came across this in a book, and I'm wondering why the following language is regular? $$ L = \{a^nww^R: n \geqslant 0, w \in \{a,b\}^3\}$$ Is it correct to say that $$ \{a^n : n \geqslant 0\} $$ is a ...
0
votes
2answers
48 views

Regular expression for a palindrome of finite length?

I have a language $$ L = \{ww^R, w \in \{ab\}^5\}$$ I know this is a regular language because it is finite (since w can only be of length 5). I want to prove it's a regular language, so I'd create a ...
1
vote
1answer
26 views

I'm asked to draw DFA for this {$\epsilon$, 0} however I do not understand what {$\epsilon$, 0} mean

I'm asked to draw a DFA of this {$\epsilon$, 0} but have no clue what it means. Can someone help me understand what the automata is supposed to do? I know that $\epsilon$ is the symbol for empty ...
1
vote
2answers
27 views

can more than two arrows point towards the same state from other states in a DFA?

Is something like this possible: You have state A,B,C all pointing towards accepting state D. Is this allowed? Where online can I find a list of rules that define how an automata must be drawn or ...
0
votes
1answer
36 views

$\text{DSPACE}(O(1))=\text{REG}$ Proof?

I want to know why $\text{DSPACE}(O(1))=\text{REG}$, especially in the direction of why all languages in $\text{DSPACE}(O(1))$ can be recognized by a finite automaton. I've thought for some time and ...
0
votes
0answers
66 views

Converting CFG to GNF problem

I have a big problem with converting GNF example. This is my CFG $ S \to AS\mid BS\mid \lambda\\ A \to aC\mid BCA\mid c\\ B \to AB\mid b\mid \lambda\\ C \to S\mid d $ I simplified the CFG by ...
2
votes
1answer
26 views

State complexity of converting epsilon-NFAs to NFAs without epsilon transitions

I am well-aware of the result showing that one can convert an epsilon-NFA (that is, an NFA with epsilon transitions) $A$ to an NFA without epsilon transitions $A'$, where $L(A) = L(A')$. Is there a ...
-1
votes
1answer
82 views

Automata that respect the condition {w|w contains at least two 0s and at most one 1}

we have the alphabet {0,1}. {w|w contains at least two 0s and at most one 1} It tried this: (However I'm not sure if it's correct. If it's incorrect why?)
0
votes
1answer
31 views

I'm trying to understand DFAs is my DFA correct in this question if not why?

I have the following alphat {0,1}. I'm told to draw a DFA which fulfills the following: {w|w starts with 1 and ends in 0} This is the DFA I came up with.
1
vote
1answer
38 views

How to create a regular expression for this language?

I have a language: $$ \{a^jb^k \mid j \neq k \text{ and } j \equiv k \pmod 3 \}$$ I want to prove that this language is regular. My first thought was to create a regular expression that accounts for ...
0
votes
0answers
14 views

Are DPDAs accepting on final state equivalent to DPDAs accepting on empty stack equivalent? [duplicate]

Say I have a string x that is accepted by some DPDA P that accepts empty stack. Intuitively it's seems impossible for P to accept any string x.y for any y != epsilon. The below DPDA accepts on final ...
1
vote
0answers
19 views

Chomsky hierarchy for finite state transducers

In this question in the first answer someone mentions a "special transduction hierarchy". I cannot find anywhere anything about it. Could someone point me to resources on this topic?
-1
votes
1answer
41 views

Turning a regular expression into a DFA

i'm studying for an exam i'll have soon and i don't understand how to draw a DFA for a regular expression, i asked my professor by mail but he doesn't asnwer... In the courses available on my college'...
-2
votes
1answer
25 views

Minimization of automata with dead state

I am supposed to minimize the following DFA automa, which contains dead state: But after the minimization of the automata, it stayed the same. Is it correct?
2
votes
1answer
58 views

Two-way finite automaton: How does the automaton remember the state

I have been going through a theory of Two-way finite automatons and I did not understand the given example when there were a DFA A = (Q, Σ, δ, q1, F). the 2-DFA B = (Q ∪ Q| ∪ Q|| ∪ {q0, qN, qF}, Σ ∪ {#...
0
votes
2answers
36 views

Turing Machine state going to itself

Hey guys in a turing machine can a state go to itself by reading a letter. For example, q2 reading a 'c' to go to itself. Is that possible? Or does it need to read a tape alphabet, such as $ to ...
1
vote
2answers
120 views

Conversion of nfa with self-loop to one without self-loop

For every nondeterministic finite state automata that has self-loop(s), there exists an equivalent nfa that does not have any self-loop. How can we prove this statement in a general basis without the ...
1
vote
0answers
39 views

How to generate a DFA that recognizes a non-regular Grammar

How would you convert the following grammar to a DFA that recognizes its language? \begin{align} &G = (\{S,A,B\},\{0,1\}, S, P)\\ &P\colon &&S\rightarrow A1B\\ &&&A \...
0
votes
1answer
77 views

Multiple paths for a accepting string in NFA?

If a string(w) is accepted by an NFA, then corresponding to w, can there be multiple paths each starting from the start state and ending at an accepting state?
0
votes
1answer
34 views

Automaton-based model checking on finite traces

I want to check whether a formula in finite LTL is valid on a finite, linear trace. For infite traces I would create a Kripke structure of the trace and a Büchi automaton for the negated formula, ...
1
vote
1answer
36 views

Construct regular expression that contains the substring

I need to write a regular expression for the following set of strings on Σ = {a, b, c} in which the number of b’s is even, and contains abcba as a substring. So far, the even number of b's can be ...
0
votes
0answers
26 views

If T is a Turing Machine, what are the languages Accept(T), Reject(T) and Loop(T)?

I have the following Turing machine: I am asked what are the langauges accept(T), reject(T) and loop(T). This seems to me a trivial question as from the looks of it, accept(T) is the language of all ...
0
votes
0answers
46 views

Construct a DFA with reduced states equivalent to 10 + (0 + 11)0*1

I have found this question in a book. I could convert it into its equivalent DFA. But the problem is with the "reduced state" part. I think the answer given in the book is wrong. What would be the DFA ...
0
votes
2answers
37 views

convert RE to NFA

The Regular Expression i am having trouble with is the following a(b|bcc*)*c. My main concern is what do i do with the c*? I can lay the rest of the diagram correctly (i think) but that part is ...
1
vote
2answers
33 views

Minimisatiom using Myhill-Nerode Theorem

I have recently studied the Myhill–Nerode theorem and while applying it to minimize these FSMs, I encountered a problem. Is it always the case that the final states should be grouped together because ...
0
votes
0answers
47 views

Constrained (linear) NFA-epsilon to DFA conversion

Goal: convert NFA -> DFA Overall goal: see if the intersection of 2 of these NFAs is empty. This will be done by converting to DFAs then DFA intersection. input NFA: multigraph between states (each ...
1
vote
1answer
21 views

Path NFA-eplison to DFA conversion

Does a path (as in path graph or linear graph) NFA-epsilon have a simpler or more efficient algorithm other than the subset construction to convert to a DFA? The only simplifications I have come up ...

1
2
3 4 5
28