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.

Filter by
Sorted by
Tagged with
1
vote
1answer
79 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 ...
-1
votes
0answers
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 ...
3
votes
1answer
32 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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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, ...
0
votes
0answers
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 ...
2
votes
2answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ?
-1
votes
1answer
48 views

I can't get the commands? each of which includes $~\$~$ instead of $~\epsilon~$ of the pushdown automaton

The pushdown automaton is given as the below diagram. What I know are as below. $$ 1,0 ~\texttt{->}~ \epsilon_{} ~~ \leftarrow~~ \text{As 1 is inputted then 0 will be popped from the stack} $$ $...
-1
votes
1answer
33 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 ...
-1
votes
2answers
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 ...
0
votes
1answer
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$ ...
0
votes
1answer
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 ...
0
votes
1answer
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?
-1
votes
1answer
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 ...
1
vote
1answer
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 ...
-3
votes
1answer
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: ...
-3
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
55 views

Is $(L_1^c \cup L_2^c)^c$ context-free or context-sensitive

I came across the following question: Let $L_1$ be a regular language and $L_2$ be a context-free language. Let $L_1^c$ and $L_2^c$ be their complements respectively. What can be said about $(L_1^c \...
2
votes
1answer
60 views

How to prove the same states are repeating in Synchronizable DFA?

I'm trying to prove the if $𝑀$ is a $𝑘$-state synchronizable DFA, then it has a synchronizing sequence of length at most $𝑘^3$. first I have to prove that if a string syncs two states, then its ...
0
votes
1answer
82 views

How to describe the language of an automaton in plain English?

How do I describe the following automaton in plain English? The only thing that I can think about when explaining in plain English would be the states, alphabet, start, accepting state, but I think ...
0
votes
1answer
22 views

Prove that grammar accepting arithmetic expressions is not regular

I created a grammar which accepts all arithmetic expressions consisting of $+,-,*,/, (, )$. I created the following grammar: $S \rightarrow M+-M$ $+-M \rightarrow +M+-M$ $+-M \rightarrow -M+-M$ $+-M \...
0
votes
1answer
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 ...
0
votes
0answers
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: ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
2answers
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 ...
1
vote
1answer
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. ...
0
votes
1answer
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 ...
2
votes
2answers
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 ...
0
votes
1answer
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 ...
-2
votes
1answer
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$ ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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> ...
1
vote
1answer
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,...
0
votes
1answer
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 ...
4
votes
1answer
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 ...
0
votes
0answers
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 ...
3
votes
0answers
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 ...
1
vote
1answer
37 views

Turing machine generating $a^b$ for given a and b

I want to draw an state diagram for a Turing machine such as: If "a" and "b" are the inputs, output in tape will be $a^b$. I saw many Turing machines that output: $a+b$ $~~$ ,$~~$ $...
0
votes
0answers
34 views

Prove language is not Turing-recognizable using contradiction

Show that the language L = {<M>| M is a TM and does not accept <M>} is not Turing-recognizable. Note: Prove by contradiction. No need for reduction. This is the problem I am trying to ...
0
votes
1answer
36 views

DFA for language

I want to give a DFA for the language which contains the words X ∈ {0,1,2}* for which the number of 0's + number of 1's is even AND the number of 1's + the number of 2's is odd. I tried many ...
0
votes
0answers
23 views

Finding the language of a given CFG

I'm trying to find the language of the given CFG $S \to aB \mid bA \mid a \\ A \to bAA \mid aS \\ B \to aBB \mid bS$ I understand that the productions $S \to aB, S \to bA, A \to aS$ and $B \to bS$, ...
0
votes
0answers
30 views

Construct a PDA that recognizes $L = \{w : w \neq a^n b^n : n ≥ 0\}$

I'm trying to find the PDA of the above language. I understand that this is the complement of the language $L_1=\{w : w=a^nb^n : n\geq0\}$ However, I can't understand the idea behind constructing the ...
1
vote
1answer
26 views

Complement of equality problem of Turing machine is recognisable or not

Complement of equality problem of Turing machines is unrecognisable or not-recognizable but How?. As per my knowledge it is recognisable if you can decide its accept condition but not Reject and ...
-1
votes
1answer
38 views

PDA for the language { $a^i b^j c^k \mid i,j,k \geq0, 7j = 5i + 6k$ }

I have seen this similar question but I can't seem to apply the same technique for the equation $7j = 5i + 6k$

1
2 3 4 5
31