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,524
questions
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$
