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
0
votes
0answers
17 views

Use ML to create a graph

I'm currently looking for literature/papers on machine learning techniques to create structures. In detail, I want to generate finite automata (NFA, DFA), which are useful for student-exercises. So I ...
-1
votes
2answers
56 views
+100

Is automata concept theorized in computer science and what would be a simple example?

I understand the terms automata or automaton to mean "self operating machine". I can't think of any such "machine" besides maybe (if it is even a machine and even exits) cyclic universe of a big-bang-...
1
vote
2answers
72 views

Can I apply Rice's theorem to decide decidability status of these languages?

I came across these languages: A Turing machine prints a specific letter. A Turing machine computes the products of two numbers I was guessing whether I can apply Rice's theorem to decide upon above ...
0
votes
0answers
16 views

Possible number of DFAs, NFAs, DPDAs, NPDAs, NDTMs and DTMs for various input parameters

I came across problem asking for possilble number of DFAs for a given number of states and alphabet. I started guessing if we can find possible number different automatas for given number of states, ...
0
votes
1answer
35 views

No nonfinal states in NFA

I know that if there are no non-final states in DFA then the language accepted is $\Sigma^*$. What will happen if there are no non-final states in an NFA? Can we say it also accepts $\Sigma^*$? Can ...
-1
votes
0answers
20 views

Closure Properties of CFL (Context-Free-Language) [closed]

Show that L = {w ∈ {a, b, c}∗ | |w|a = |w|b = |w|c} is not context-free by using the closure properties of the context-free languages. Note: make sure to use the closure properties of the context-free ...
0
votes
1answer
34 views

Turing recognizable but not Turing decidable language cannot have TM do not halt on infinitely many inputs

Sorry, I think I misunderstand the question, It should read as if $L$ is turing-recognizable but not decidable, then there exists infinitely many input that any TM will not halt on it...
-1
votes
0answers
39 views

set difference of two non regular languages

Lets say we have $L_1$ and $L_2$ two non regular languages . is $L_1 $\ $L_2$ is always non-regular languages? I thought about $L$ \ $L^c$, but i'm not sure
0
votes
1answer
42 views

Maximum number of configurations of Turing machine after $n$ moves

I came across following question: What are maximum number of configuration of Turing Machine after $n$ moves? The answer given was: $k^n$, where $k$ is a branching factor. And that "branching ...
0
votes
0answers
9 views

How FA, PDA and TM emulate each other

I came across following points at various sources: A one-stack Turing machine is really a DPDA. Turing machine with two stacks can accept any recursively enumerable language (and hence is as ...
0
votes
0answers
20 views

Is the language $L$=$\{<D_1,D_2> | D_1,D_2$ are DFAs over $\{0,1\}$ and $L(D_1) \subseteq L(D_2)\}$ decidable?

I came up with an algorithm to decide this language, but not sure if it is correct? ...
0
votes
0answers
15 views

Showing different derivation trees for same string X

So I understand how to do this with there being multiple symbols in each possible production, but when it is singular, it seems to get more complicated, or I am overthinking it? Would the left-most ...
-1
votes
0answers
16 views

Help in converting NFA to regular expression [duplicate]

Hi I don't understand how to convert NFA to regular expression in the question below. Can someone help me to solve and understand example below
0
votes
1answer
22 views

Closure of regular languages under “inverse second half”

Theorem. Show that if $L$ is regular, then so is $$ \varphi(L)=\left\{w \in \Sigma^{*} \mid \text {there exists an } \alpha \in \Sigma^{*} \text { with }|\alpha|=|w| \text { and } \alpha w \in L\...
1
vote
1answer
14 views

NPDA question about accepting condition

Will an NPDA accept a string that reaches a final state but does not have all its input consumed yet?
0
votes
0answers
22 views

Minimal DFA for “$n$th character from the right is $a$” [duplicate]

I am given the following regular expression, which accepts all strings over $\{a,b,c\}$ whose $n$th character from the right is $a$: $$ (a|b|c)^*a(a|b|c)^{n-1}. $$ The exercise asks for the number ...
1
vote
1answer
42 views

What kind of language does the following DFA accept?

can anyone please describe the language this FA accepts? thank you
2
votes
1answer
35 views

Does this argument prove CFLs are not closed under union?

Context free languages are not closed under complementation. This follows from their property of non-closure under intersection: If CFLs were closed under complementation, then they must have also ...
0
votes
1answer
26 views

Designing a PDA that keeps track of the stack size

Would it be possible/legal to design a PDA that can use the stack as a way to keep track of the number of inputs seen? (i.e the size of the stack would act as some sort of counter). What I was ...
0
votes
0answers
32 views

Pushdown Automata for number of a less than 2 times number of b

Suppose we want to design a pushdown automata for $L=\{x \in \{a,b \}^{*}:|x|_a<2|x|_b \}$, can anyone check whether my automata works? we have 4 states $\{q_0,q_1,q_2,q_3 \}$, three stack symbols ...
1
vote
1answer
100 views

Is Half - Palindrome subset of a context-free language context-free?

Suppose we have $L$ being a context-free language. Let $L'=\{x \in \Sigma^* | xx^R \in L \}$, is $L'$ context-free as well? I know that if $L$ is regular then $L'$ is regular as well by constructing a ...
1
vote
1answer
18 views

Are number of states in a NFA same as Pumping length?

So i was reading a post on Minimum pumping length of regular language where Yuval Filmus has proved that a pumping lemma might have lesser number of states than a minimal DFA. But What about NFA's? ...
0
votes
1answer
91 views

Prove $\epsilon(S\cap T)\subseteq S \cap T$

Suppose there are sets $S\subseteq Q, T\subseteq Q$ such that $T=\epsilon (T),S=\epsilon (S)$. Prove $\epsilon(S\cap T)\subseteq S \cap T$ Definition of $\epsilon$- closure for epsilon NFA is: ...
0
votes
0answers
38 views

How to find a context-free grammar from a difficult language? [duplicate]

Some Languages are trivial to find their respective context-free grammar. Like for example $ L= \{a^nb^n: n \geqslant 0\}$. However some are really difficult to solve. I would like to have some advice ...
2
votes
1answer
28 views

$L=\{a^ib^i|i\geq0\}$, cfg for $L^2$

$L=\{a^ib^i|i\geq0\}$, cfg for $L^2$ can you write cfg for $L^2$ where $L=\{a^ib^i|i\geq0\}$? the professor's answer sheet says it's $S\to AA\\ A\to aAb|\lambda$ but I think it is wrong because two ...
3
votes
1answer
70 views

Prove that there isn't a DFA characterized by (a*)+(b*) for which |Q| = 3

Let $R=(a*)+(b*)$ be a regular expression. Prove that there cannot exist any DFA $M=(Q,\Sigma,\delta , q0, A)$ such that $|Q| = 3$ and $L(M)=L(R)$. The problem is, I think IT IS possible to construct ...
1
vote
1answer
192 views

Let M be an $\epsilon$-NFA and let $S\subseteq Q$. Prove $\epsilon (S) = \epsilon (\epsilon (S))$

Let M be an $\epsilon$-NFA and let $S\subseteq Q$. Prove $\epsilon (S)= \epsilon (\epsilon (S))$. I would like to prove this by contradiction but I don't know if my idea is correct. Definition of $...
0
votes
1answer
52 views

DFA for language of all strings avoiding 'aa'

I'm trying to draw a dfa for this description The set of strings over {a, b, c} that do not contain the substring aa, current issue i'm facing is how many states to start with, any help how to ...
1
vote
2answers
115 views

Describe construction of finite automata that accepts the language Double-Letter(L)

Describe construction of finite automata that accepts the language Double-Letter(L), where Double-Letter(L) is in the language of words from L, except each letter in the word appears twice. So $...
1
vote
1answer
22 views

$\epsilon$-transitions in NFAs

I am reading "Introduction to the Theory of Computation" (2ed) by Michael Sipser. In Example 1.35, it says the NFA accepts $\epsilon$, which I understand, since the state can stay at $q_1$ upon input ...
2
votes
1answer
35 views

Showing the following language is decidable

Let $BAL_{DFA} = \{<M> \mid M \text{ is a DFA that accepts some string containing an equal number of 0's and 1's } \}$ Show that $BAL_{DFA}$ is decidable. Generally such questions seem to be ...
2
votes
1answer
283 views

show that if L is a regular, then drop(L) is a regular

I am trying to prove the following problem, but honestly I don't know what "proof" is considered a good proof. I tried to prove it by constructing an NFA that start with w1 and ends with wk, but I ...
1
vote
1answer
73 views

How to find out the complement of a language of turing machines?

With only using our thinking. What do I have to think about when finding a complement of a Turing machine for example. L={M∣M is a TM that halts on empty tape after even transition steps} What's the ...
4
votes
3answers
236 views

Black Box Decision problem for NFA

Suppose we are given an NFA $M$ (without $\epsilon$-transitions) that we only know the alphabet $\Sigma$ and the number of states $|Q|$ but we do not know any other details of the NFA. We want to ...
1
vote
1answer
23 views

Equivalence from multi-tape to single-tape implies limited write space?

Suppose I have the following subroutine, to a more complex program, that uses spaces to the right of the tape: $A$: "adds a $ at the beginning of the tape." So we have: $$ \begin{array}{lc} \text{...
2
votes
1answer
29 views

Büchi automaton to Linear Temporal Logic

Given a Büchi automaton what is the procedure to build an equivalent LTL formula? And what is its size? I'm looking for references but I haven't found them so far.
1
vote
1answer
60 views

Proving a DFA recognizes a language using induction

The following DFA recognizes the language containing either the substring $101$ or $010$. I need to prove this by using induction. So far, I have managed to split each state up was follows: q0: ...
-2
votes
1answer
28 views

Need help Understanding Concept of Pumping Lemma & Regular Languages

So my professor suddenly decided to make our homework difficult. He did not provide any examples or ways to proof so now I've been stuck on this for a while. I'm not asking for the solution but ...
1
vote
1answer
38 views

If you have a DFA M, how do you construct a new NFA that accepts L(M) and {e}?

Suppose you're given a DFA $M$ with a 5 tuple of $(Q, \Sigma, \delta, q_0, F)$. How do you construct an NFA that accepts $L(M)$ and $\{\varepsilon\}$, the set containing the empty string? I know that ...
1
vote
1answer
47 views

How can I show this language is Regular? (Foundations of computing) [duplicate]

Σ(alphabet) contains 3x1 column matrices [[0],[0],[0]], [[0],[0],[1]] , [[0],[1],[0]]... [[1],[1],[1]] such that each element in the language is a THREE SET of the columns where the bottom row is ...
-1
votes
1answer
73 views

How to generate Deterministic finite automaton for given language

Problem: Write a program which generates Deterministic finite automaton which accepts given language. Language is defined with alphabet and start/end sub strings. For example: Alphabet={a,b,c}; start ...
3
votes
1answer
65 views

Is LOG(L) Regular? [duplicate]

For a language L $\subseteq$ $\Sigma$* , define LOG(L) = { u $\epsilon$ $\Sigma$* | $\exists$ v s.t. |v| = $2^|$$^u$$^|$ and uv $\epsilon$ L}. Show that if L is regular so is LOG(L). I was trying to ...
0
votes
1answer
102 views

A regular expression for all strings that have exactly one double letter in them?

Why is the answer (b + /\)(ab)*aa(ba)*(b + /\) + (a + /\)(ba)*bb(ab)*(a + /\)? I'm confused and I request guidance
1
vote
1answer
45 views

Automata with minimal number of states using reverse

So, by the Bzozowski theorem, if A is DFA det(rev(det(rev(A))) would have minimal number of states. And for the most of them work. But for this example, I can't figure out why it doesn't. I have an ...
0
votes
0answers
49 views

Why is it not possible to prove the equivalence of nondeterministic and deterministic Turing Machines the same way as for NFAs and DFAs?

I found en excercise asking this question. I know that for proving the equivalence of NFAs and DFAs we can use the conversion through subsets, and that for proving the equivalence of nondeterministic ...
0
votes
1answer
20 views

Lexicographic Order of Expression [Automata Theory]

what will be kleene star "expansion" of expression $a^*b^*$ in lexicographic order? I'm confused and I really want to clear my concepts so I can proceed further
2
votes
1answer
50 views

Prove: If finite automata M with k states accepts a string with at least k characters, then the language L(M) is infinite

I need to prove that if finite automata $M$ with $k$ states accepts a string with at least $k$ characters, then the language $L(M)$ is infinite. I have no idea where to start. Any suggestions?
1
vote
1answer
33 views

How to propose a method to construct an automaton?

Given $0 \leq m < k$ and $p \geq 2$ it's defined $$A_{k,m,p} = \{ \alpha \in \{0,1,\dots,p-1\}^* | \alpha \text{ is a p-ary representation of } x \backepsilon x \text{ mod } k = m \}$$ It is ...
0
votes
0answers
26 views

Uncommon case in Arden's lemma $q_{2} = 1q_{2} \cup 0q_{2}$

I'm trying to get the regular expression of an automata but an state has a form that I don't know how to solve, the form on its simplest example is: $$q_{2} = 1q_{2} \cup 0q_{2}$$ What's the ...
0
votes
0answers
32 views

If $L^2$ is regular. Does that imply L is regular [duplicate]

If $L^2$ is regular. Does that imply L is regular. I think L need not be regular. But I can't find any example where L is not regular but $L^2$ is regular. My teacher told me an example where L={$0^...