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,506
questions
0
votes
1answer
27 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 ...
-1
votes
0answers
25 views
How to check whether a language is regular or not? [duplicate]
I am given expressions such as
\begin{align}
L_2 &= \{ a^n b^{n!} \}, \\
L_3 &= \{ abcva^n \mid v \in \{a,b,c\}^*, n \in \mathbb{N}, n \text{ is even}, |v|=n/2 \}.
\end{align}
0
votes
1answer
21 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
27 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 ...
-2
votes
0answers
15 views
The set of all strings of 0’s and 1’s such that no prefix has more 1’s than 0’s [duplicate]
What strings does this represent? Is it saying that the first half of the string can't have more ones than zeroes? If that's the case what do we do with an odd length string?
0
votes
0answers
13 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
35 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
28 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
53 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
28 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
23 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
52 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
33 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
45 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
36 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
11 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
23 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
31 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
36 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
40 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
23 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
29 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
32 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
32 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
31 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
21 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
27 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
23 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$
0
votes
1answer
26 views
Proving undecidability of a language with mapping reductions
I'm referring to questions like this one:
Mapping reduction to show NeverHalt is undecidable
I understand with Turing reductions, you have to use oracle calls of the unknown language you're trying to ...
2
votes
1answer
35 views
$\omega$-automata where string is accepted iff a final state is accessible from starting state
I am wondering if $\omega$-automata with the following acceptance condition are valid.
An input string is accepted iff one of the final states occurs at least once.
This differs from Buchi automata in ...
1
vote
2answers
51 views
Proving that a language is a CFL
Assume that $L_1 \subseteq \Sigma^*$ is a CFL and that $y \in \Sigma^∗$ is a string.
I need to prove that the language $L_2 = \{x \in L_1 \mid x \text{ does not contain $y$ as substring}\}$ is a CFL.
...
1
vote
1answer
29 views
Proving Undecidability with reductions - Why do some proofs not use an Oracle?
I'm specifically referring to this group of questions here: https://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf
So as I've learnt it, say we want to prove a new Language L is ...
0
votes
0answers
28 views
Convert the Finite Automata (FSA) into its equivalent regular expression, using stepwise minimization
I was doing an assignment of Theory of automata but while doing this question I am stuck there is no such state that can be eliminated even from transition table. I am very confused and stuck please ...
0
votes
1answer
35 views
Prove that the following language is not a regular language
Prove that the following language is not a regular language:
$L = \{ 0^x1^y | x, y \geq 1\text{ and } x \geq y\vee (x < y \wedge y \mod x = 0)\}$
Is there anyone to prove this ?
0
votes
1answer
23 views
Extended NPDA implementation
In Formal grammars course we have a task to implement an extended NPDA (a pushdown automata where taking any amount of symbols from the stack is allowed (including ε) and it can be in several states ...
2
votes
2answers
63 views
Infinite prefix-closed context-free languages contain an infinite regular subset
The Problem:
Say that a language is prefix-closed if all prefixes of every string
in the language are also in the language. Let C be an infinite,
prefix-closed, context-free language. Show that C ...
0
votes
1answer
41 views
$L^{\prime}=\{x \# y \mid x y \in L, y x \notin L\}$ where $L$ is regular
Hey I'm trying to prove that the following Language is regular so far couldn't find a way, hope someone can help me $L^{\prime}=\{x \# y \mid x y \in L, y x \notin L\}$ where $L$ is regular.
1
vote
1answer
38 views
An algorithm to check if two DFA are disjoint
What is the algorithm to check if two DFA are disjoint? I want to know if there exist any string accepted by both automata.
0
votes
0answers
23 views
Worst case of subset construction (NFA to DFA) [duplicate]
I am wondering what generic example there is so that an NFA with $n$ states results into a DFA with $2^n$ states after the conversion by the subset construction. I know there is the example by ...
1
vote
0answers
24 views
How to prove existance and construct finite-state transducer between two different FSM?
For example I have 2 simple FSM. I will use regular expression for clarity.
...
0
votes
1answer
38 views
Is the language $\{a^n b^m \mid 2n + 3m \le 1000 \}$ regular?
We have a language $$ L = \{a^n b^m \mid 2n + 3m \le 1000 \} $$
Is this language regular?
I'm trying to disprove this using the Pumping Lemma, but it didn't work.
assume I say x = $x=a^{h}$ and $y=a^{...
1
vote
0answers
12 views
What to do with operators with the same precedence in an unambiguous grammar?
I'm trying to create an unambiguous grammar for a calculator that uses $+$, $-$, $*$, $/$ and $()$.
From watching videos and reading articles online, I understand how to create the grammar with $+$, $*...
1
vote
1answer
34 views
Given two DFA's accepting the same language, does one have to refine the other?
I have a logical question that I can't quite crack:
Given two automata accepting the same language $L$, does one have to refine the other?
In other words, if $A_1$ and $A_2$ both accept $L$, with ...
1
vote
0answers
40 views
Different PDA design processes — both valid?
This video shows how to design PDA from a CFG:
https://www.youtube.com/watch?v=ZImtQBMSW_Y
Basically, we always have 4 basic states, and one of them is a "hub" for loops that implement ...
0
votes
1answer
17 views
Decidability of directed strongly connected graphs
Consider the problem of determining if a directed graph is strongly connected.
How to phrase it as a language and prove that it's decidable.
My Thoughts :
To think of decidability given a graph I ...
-2
votes
2answers
23 views
Regular expression of an FA
If we convert an NFA to a DFA, is the regular expression of the DFA the same as the NFA?
I know the difference between an NFA and DFA and the algorithm to convert an NFA to DFA
0
votes
2answers
60 views
Convert NFA to DFA
Is there a unique DFA for every NFA or there are more than one DFA an NFA can be converted to?
I've read the algorithm for converting NFA to DFA.
0
votes
0answers
45 views
What are the technical reasons for which the empty string is not allowed to be accepted by a Turing machine?
Below are the excerpts from the automata text by Peter Linz.
Definition 9.3
Let $M = (Q,\Sigma,\Gamma,\delta,q_0,\square,F)$ be a Turing machine. Then the language accepted by $M$ is
$$L(M) = \{ w \...
2
votes
1answer
54 views
Language of decimal encodings of cubes is not regular
Prove that the language that consists of cube numbers as strings is not regular.
I wanted to use pumping lemma but couldn't
$$0, 1, 8, 27, 64, 125, 216, \dots$$
