# Questions tagged [automata]

Questions about mathematical devices that read an input stream symbol by symbol and use a state transition map to produce an output stream, maybe using secondary storage.

1,493 questions
Filter by
Sorted by
Tagged with
42 views

### can a DFA with only final states be minimized?

I need to construct a DFA for a certain language with as little states as possible. so far my "best" solution contains 15 states. however, people claim it is doable in 7 states only. I tried for ...
44 views

### Closure on regular languages

A) Let $L$ be a regular language. according to the theorem there is an DFA which accepts the language. Describe shortly how to change the DFA to NFA which Accepts $L^R$, where R is reverse. There is ...
46 views

277 views

### Prove the following language is regular?

Assume $L_1$ is a regular language, and define: $$L = \{wcv ∈ \{a, b, c\}^* \mid |w|_a + 2|v|_b ≡ 3 \bmod 5, w, v ∈ L_1\}.$$ Show that $L$ is regular. I first tried to prove by showing that the ...
87 views

### Can one determinize finite automata over infinite trees?

I'm currently considering deterministic, nondeterministic, universal, and alternating automata over infinite words and trees, with Büchi, co-Büchi, Muller, Rabin, Streett, or parity acceptance ...
337 views

### Proving a language is not regular using Myhill Nerode Theorem

Let $L = \{\alpha\in\{a,b,c\}^{*} \mid \alpha \text{ is palindrome}\}$, show that $L$ is not regular using Myhill-Nerode relation. I don't know how to show that $L$ has infinite equivalence classes ...
105 views

### Design a DFA recognising the following language

Design a DFA over alphabet (a,b) such that for all it's string no prefix contain two more a's than b's and two more b's than a's and the number of a's is equal to b's. Is it possible to design a DFA ...
170 views

### Design a DFA for the language L = {w | w contain 2 a’s at any position and greater than 3 b’s at any position, w ϵ {a.b}*}/

I do not understand this question,because for saving Number of a's and b's memory is required,which FA does not provide.could anybody please explain this?
56 views

### A state space for river crossing puzzle

I am solving the river crossing puzzle with 6 participants. You must transfer all the people across the river in this flash game respecting the following rules: The ferry can carry no more than 2 ...
151 views

### Converting DFA to Regular Expression Using State Removal

I'm trying to convert the following NFA to a regular expression. I've attached my work below and end up with the expression $aa^*bb^*$. As far as I can tell, this doesn't seem correct but I've been ...
74 views

### NFA-$\epsilon$ extended transition function for inverted strings

It is well known that in $NFA-\epsilon$ the extended transition function is defined as it follows: \begin{align*} \hat\delta: Q &\times \Sigma^* \rightarrow \mathbb{P}(Q) \\ \hat\delta(q,\epsilon) ...
50 views

### How to write a regular expression that excludes certain strings? [duplicate]

It's a homework problem. Assume $\Sigma = \{a ,b\}$, I am asked to construct a regular expression that does not have both the substrings bba and abb. My idea was: construct a regex that matches ...
363 views

### Large DFA to regex?

For an assignment for one of my courses, one of the questions is to provide a regular expression for the language: "the set of strings such that the number of 0’s is divisible by six, and the number ...
109 views

### Minimization of DFA- one state mark or no mark?

I want to know, what if the DFA is merged states. So if my DFA starts with q0 and then have (q0,q1) state it goes to with an 'a' for example. How do I do the table filling method. I tried to rename ...
410 views

### Prove that a language is regular

I'm working on an example which says that a string x is obtained from a string w by deleting symbols if it is possible to remove zero or more symbols from w so that just the string x remains. For ...
81 views

### “If A is nonregular, then there exists a nonregular language B such that A ∩ B is finite.”?

Is the statement true? I feel that the statement is true. I want to prove it but I don't know how to start the proof. Any help would be appreciated.
74 views

### Is it possible to constract Moore or Mealy machine with a different size of input and output?

Is it possible to constract Moore or Mealy machine to take input tape: 0011 and output: 00001111 (or vice versa). In other words, input and output have different size. I want to construct FSMs to ...
189 views

### Why does this NFA having an empty symbol

I'm trying to understand the difference of DFA from NFA I have this example in my coursebook Are the empty symbols at the start necessary? or can we do away with them to have something like this
115 views

### Constructing an NFA for a language defined over $\Sigma = \{0, 1\}$

The language is defined as $$L = \{0^n10^m10^q \mid n,m,q \in \mathbb{N}, q \equiv nm \mod 5\}.$$ Can someone help me get started on this question? I don't know what part of the question I should do ...
59 views

### What are HP and MP in this context?

From Kozen's Automata and Computability, 3ed, lecture 32 p. 328: What are HP and MP in this context? I tried looking around and this text says: How did the halting problem and membership problem ...
60 views

### The PDA have to finish reading the input?

I have PDA which has final state that accept 'c' char, and there isn't any cross to other state. The input abca will accept, because there is 'c', or the PDA would stuck?
147 views

### Why L' is not regular?

$$L'=\{ww|w\in L\}$$ I need to give an example of regular language L for which the concatenation of 2's $w$ gives $L'$ which is not regular. How can I give such an example if according to closure ...