# 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,525 questions
Filter by
Sorted by
Tagged with
4 views

### Prove that the following languages are not regular by providing a fooling set

Prove that the following languages are not regular by providing a fooling set. You need to provide an infinite set and also prove that it is a valid fooling set for the given language
84 views

### What is the meaning of the pipe symbol here?

I am reading Distributed Algorithms by Nancy Lynch. In chapter 16, I came across the pipe symbol. Does this mean the same as "or" in some programming languages or could someone explain that ...
35 views

### A formal proof of Arden's Theorem [duplicate]

I have been searching internet for a correct proof of Arden's Theorem and have searched some book also. Many proofs seem to be completely wrong, filled with fallacies and can't trust what is written ...
33 views

### Can a non deterministic finite automaton go into infinite loop?

Here is the exact same question but on deterministic finite automaton. The case for deterministic finite automaton is simple. For each state only one transition is possible for each input symbol and ...
53 views

### Regular language closed under homomorphism

I am trying to solve problems from the textbook 'Introduction to the Theory of Computation' by Micheal Sisper, 3rd edition. I am attempting to show various properties of regular languages and their ...
16 views

### Mapping reduction properties exercise

I am having trouble understanding how to conclude if the statements are true or false, I would really appreciate your help. We know about three languages, A, B and C. There exists a mapping reduction ...
27 views

### Find a transducer that maps a given deterministic process to another

Let $S$ denote a deterministic process which generates a certain string, described through a Hidden Markov Model. More specifically, for a process with alphabet $\mathcal{A}$ and $n$ hidden states, ...
13 views

### Cannot figure out what I am doing wrong with Mealy to Moore conversion

I've spent a lot of time on this and still cannot see what I am doing wrong, will appreciate any help. Below the source Mealy machine: According to the solution, there should be two 1s in the ...
90 views

### Whats the signifgance of Conway's Game of Life?

I've seen Conway's game of life mentioned in different circles and it seems many people (myself included) have made an implementation of it at one point or another. Other than the fact that it is ...
27 views

### The same transition twice in Pushdown automata (PDA)

If we want to design a PDA that accepts all words those the first half equals reverse of the second half and there is a '#' between them, "ab#ba" for example. We start push each letter we ...
27 views

### Does finding a reversal of a regular expression by automata need automata to be a DFA?

If I want to find the reversal of a regular expression using an automata, Do I have to transform the automata to DFA if it wasn't ?
48 views

34 views

### Design the finite DFA where 5 divides 2i+3j

a) For $\sum =\{0,1\}$ , design a deterministic finite automaton $M$ accepting the language $L=\{a^ib^j:i,j\ge 1, \text{5 divides (2i+3j)}\}$ b) Prove that ypur automaton exactly accepts the language ...
61 views

### Is this grammar well-defined? How do I prove the language generated by it is regular?

I have the following problem statement: Is G well-defined here? I am unsure of this since there's no production rule for $X, Y, Z$, and this confuses me a bit. And secondly, how do I prove $L$ is ...
43 views

### How to check $L$ is regular or not [duplicate]

If $L=\{w \in \Sigma^*\mid w=uv,\text{ number of occurnce a's in$u$equal to number of occurrence b's in$v$}\}.$ I think $L=\Sigma^*$ because for any string in $\Sigma^*$, we can split it to $uv$ ...
22 views

### Turing machine halts on input $a^m$ with $a^{m^2}$ written on tape

I am learning Turing machine in automata. Following problem might be simple, as that's the first question on Turing machines in my textbook, however I am not sure if I am doing it efficiently. Give ...
41 views

### Prove $(aa^*bb^*)^*=ϵ+a(a+b)^*b$ using regex laws

I tried to prove this by starting at RHS: $$ϵ+a(a+b)^*b = ϵ+a(a^*b^*)^*b$$ But I dont know how to convert $(a^*b^*)^*$ to something else that will be helpful. Any ideas?
25 views

### How can I implement a Deterministic finite automaton which accepts

Problem: implement a Deterministic finite automaton which accepts 01 ∪ (2∪10*2)* ∪ <- is union symbol I have a lot of problem trying to implement that DFA, the union symbol always confuse me Can ...
159 views

### Prove that the language generated by the grammar $S \to SxS \mid a$ is inherently ambiguous

With the following grammar: $$S \to SxS \mid a$$ Is L(G) inherently ambiguous? What is the proof? I know how to prove the grammar is ambiguous but I don't know how to prove if the grammar is ...
51 views

### How can I convert from DFA in to regular grammar?

I have following information. 0 1 -> *q0 q0 q1 q1 q1 q2 q2 q2 q0 I have to convert this in to a regular grammar. I wrote this: ...
34 views

### How can I convert a Grammar to NFA?

Hello I have a task where I´m stucking at. I have to convert a Grammar to NFA. I have these information: G=(V,T,P,S) V={S}, T{0} and S -> 0S S -> 0 I can´t ...
27 views

### What is a generalized automaton that has ability to look up anything in memory from environment?

An automaton determines its next state from the current state and the next input symbol. A pushdown automaton adds a stack which you can push/pop/read from. But then there are probably a lot of ...
55 views

29 views

### What Is the Currently-Known Simplest NOR-node Directed Cyclic Graph That Produces Pi?

Any directed graph (including a directed cyclic graph or DCG) has a complexity measure. We know that NOR is a universal logic gate, in the sense that a DCG whose nodes are n-input NOR gates can ...
16 views

### Context Free Grammar to Chomsky Normal Form Help

I am trying to convert the following CFG to CNF: S -> ABS | ε A -> BSBa | a B -> Ba | a The finally result looks like this: ...
37 views

### pushdown automata question

We define a new model: A "100-PDA" is a pushdown automaton with at most 100 states and with at most 100 symbols in the stack alphabet. Prove or disprove the following statement: "There ...
33 views

### Use the CFL pumping lemma to show that this language(0^p where p is prime) is not context free

L = {0^p |p is a prime}. So was looking at the explanation at the bottom of page 5 of the following website: https://www.ics.uci.edu/~goodrich/teach/cs162/hw/HW5Sols.pdf I want to make sure that I ...
58 views

### What is appearance checking in the context of formal grammars?

As I did not find any definition of the term "appearance checking" although it is widely used, I am eager to ask as what it can be defined. Perfect would be an example using a context free ...
32 views

### Is a register machine built out of automata of some sort?

I am looking at register machines like the Random Access Machine. Wikipedia says: Random-access machine (RAM) – a counter machine with indirect addressing and, usually, an augmented instruction set. ...
25 views

### Pushdown automaton with binary stack

I have a problem where I'm asked to prove that if P is a pushdown automaton, then there exists another pushdown automaton P' with only two symbols in its stack alphabet that accepts the same language ...
63 views

### Prove the language $\{x \in \Sigma^* : \exists w \in \Sigma^* \ xww \in L \}$ for regular language $L$ is regular

Let $\Sigma=\{0,1\}$ and $L$ be a regular language. Prove that $$Z(L) = \{x \in \Sigma^* : \exists w \in \Sigma^* \ xww \in L \}$$ is a regular language. I tried to build a NFA based on the DFA that ...
37 views

### Minimum pumping length of finite language

Background Let L = {aa}. We know that the minimum pumping length of L is |aa| + 1 = 3. For this length all the three conditions of the pumping lemma vacuously hold true. Doubt Let L = {aa, aab}. Is it ...
49 views

### Finding the language generated by this grammar

I'm having problems with this. Can someone help me please. Find the language generated by this grammar over the alphabet $\{0,1\}$: $S\rightarrow BAB\mid CAB$ $BA \rightarrow BC$ $CA \rightarrow AAC$ ...
53 views

### How to draw Turing machine for multiplying a number by 2 in base 10

I'm trying to design a turing machine that given a number in base 10 multiplies it by 2. The problem seems trivial if the number is represented in binary so what I've thought is try to convert it from ...
13 views

### Research on Tree Automata/Tree Transducers for implementing Tree Generators

I would like to write from scratch a tree pattern matching algorithm. Well actually, not just a matching algorithm, and not even a tree transducer, but a sort of tree constructor that takes basically ...
24 views

### How can we solve halting problem efficiently?

I was doing exercises regarding the halting problem and there is this question where I am stuck Ques: it goes like suppose if you can decide the halting problem with a query "Is <tm,s> ...
37 views

### PDA translating $a^{m+n} b^n$ to $x^{2m+2} y^{3n}$

On my compilation theory exam we had the following problem: Construct a PDA translator (just one stack) such that it translates the language  a^{m+n}b^n \rightarrow x^{2m+2}y^{3n}, \text{ where } n,...
40 views

### Is it possible to create a NFA that accepts only n*"a" or n*"b" inputs?

I'd like to create a NFA that accepts only inputs like "aaaaa";"a";"bb";"bbb", but not like "aab";"aabaa". Is the even possible? As far as I ...
54 views

### Maximal minimal DFA for some language of n-bit strings

Notation: $M$ is a DFA; $L(M)$ is the language accepted by $M$; $\min(M)$ is the minimal automaton equivalent to $M$ derived from a minimization algorithm such as the Hopcroft algorithm; and $|M|$ is ...
24 views

### How NFA decides how to break up a string?

If we have a language K, that word w=uv, accepts. $K= \{{w \in \{a, b ,c\}^*: \ \vert u \vert_a \ \text{is not divisible by 3}}\}$. Can we land strings like aaaa ...
31 views

### Are automata useful in software verification?

I contrast the paradigm of SMT-based verification of software, such as in LiquidHaskell with the approach based on automata. To me it appears that automata are only used in the paradigm of model ...