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

### Difference between linear bound automata and a Turing machine

Can anyone give an example where a language can be rejected by linear bounded automata and accepted by a Turing machine. Is there any proof that a linear bounded automata is less powerful than a ...
18 views

### Nondeterministic Turing Machine for $L^*$

If $T$ is a Turing Machine that accept a language $L$, I want to define a Turing Machine $T'$ such that accepts the language $L^*$. An approach: $T'$ is a nondeterministic Turing Machine which has ...
98 views

### Turing Machine construction of M=wwRw form

Construct a Turing machine for M = {wvw| v, w ∈ {a, b}*, reversal(v) = w}. I tried to imagine that I will have to divide the string into 3 equal parts and check if ...
76 views

### Is this push-down automaton non-deterministic, as JFLAP states?

There is a tool called JFLAP, which, among other things, can analyze push-down automata, and find non-determinism. In this example it is detecting non-determinism in state ...
63 views

### Convert PDA by final state in to cfg

Hope you all are doing well. I want your assistance. I have a PDA which is accepted by the final state. I need to convert it into cfg. So I want to ask, If I want to first convert this into ...
21 views

Let M a finite state transducer define as : $M=<X,Y,S,\delta,\lambda>$ What we mean by quasi-linear finite automata?
25 views

Can we proof the number of NFSTs with $n$ states : $n.2^{mpn}.2^{n}$ where $p$ is the cardinal of input alphabet and $m$ the cardinal of output alphabet.
51 views

### How to show that a language is regular

I know that to show that a language is not regular, you are supposed to use the pumping lemma, but I cannot figure out how can I show that a language is regular. How would I show that the following ...
37 views

### TM for Language With a Specific Cardinality

I'm curious about how to build TM that decide and recognize languages defined by cardinality. For example, with the language $L_1$ = $\{w \in \{0,1\}^* | |w| = 1\}$ this is the language with a single ...
122 views

### When our two-state PDA constructed from CFG is non-deterministic PDA?

We can always convert our GNF-CFG/CNF-CFG to a two-state PDA but i'm wondering when our PDA is non-deterministic? i'm sure we can not make DPDA for non-Deterministic-CFL , and i suspect that same rule ...
133 views

### Finding the upper bound of states in Minimal Deterministic Finite Automata

I have a task to determine the upper bound of states in the Minimal Deterministic Finite Automata that recognizes the language: $L(A_1) \backslash L(A_2)$, where $A_1$ is a Deterministic Finite ...
53 views

### Does the order of ripping off the states matter?

Do we get same regular expressions at the end regardless of the order that we take the states step by step? Can somebody prove by exemplification?
34 views

### How to find the language and create Push down automaton if the A is continuously looping ? and will PDA accept L produced without A

Let us consider the following Context-Free Grammar G = ({S,A,B,C,D},{a, b}, S, P) with production rules P: S → SSA | Bb A → BSA B → A | Cb C → AD | Cb | ɛ D → a | b | ɛ Let L be the language ...
58 views

### PDA with more than one initial state

I'm wondering if PDAs with more than one initial states are also accepting context free languages. If found that question on this site about NFAs and would like to know if this answer is also valid ...
224 views

278 views

### Conversion of nfa with self-loop to one without self-loop

For every nondeterministic finite state automata that has self-loop(s), there exists an equivalent nfa that does not have any self-loop. How can we prove this statement in a general basis without the ...
49 views

### generate CFG from words that have even length and have at most two 0's

How to I generate a CFG from the language that have even length and have at most two 0’s L3 = {w ∈ {0, 1} ∗ | w is even length, 0<=2 } I feel stuck on meeting the criteria of maximum two 0s My ...
28 views

### Name of this 2D automata

Today I had a weird dream about a kind of automata. Each automaton has a finite 2D grid wrapped around like a torus, formatted as a table. Execution starts in one cell. Each step it executes whatever ...
191 views

### Given regular languages $L$, $M$. Is $K=\{uw | u,w \in \Sigma^*,(\exists v \in M) uvw \in L\}$ necessarily regular?

Question is as follows: Given regular languages $L$, $M$. Is $K=\{uw | u,w \in \Sigma^*,(\exists v \in M) uvw \in L\}$ necessarily regular? Thank you for any input.
106 views

### Prove that a finite language is regular

I want to prove that $L(G) = \{01; 11110; 10101; 000\}$ is regular. Is it correct if I write there exists a regular expression, which is: $(01|11110|10101|000)$? How can I also prove it using a DFA?
177 views

### Multiple paths for a accepting string in NFA?

If a string(w) is accepted by an NFA, then corresponding to w, can there be multiple paths each starting from the start state and ending at an accepting state?
106 views

### PDA for parentheses language

Construct a PDA for the language described by the following CFG: $$S \to [S] \mid \{S\} \mid \Lambda$$ How can I develop a pushdown automaton for this language?
78 views

### PDA for $L= \{w : n_a(w)+n_b(w) = 2n_c(w)\}$

I'm pretty new to the PDA topic. How do I construct an NPDA for the language $$L= \{w : n_a(w)+n_b(w) = 2n_c(w)\}.$$ I've tried all the possibilities, but I still somehow end up accepting all words.
74 views

157 views

### If L is regular language then each equivalence class is also regular?

L is a regular language. Let's say that E is one of L's equivalence classes - is it true/false that E is also regular? The equivalence relation is, from Wikipedia: "Given a language L, and a pair of ...
932 views

### Over the alphabet {a,b,c,d}, how would i construct a NFA that only accepts strings that end with a letter that is already part of the string?

I've been trying to create a NFA that accepts strings that end with a letter that exists in the string. For example abcdb, cbdd, acac etc. while strings like abc aacd etc are not accepted since the ...
261 views

### Queries regarding simulation of multi-tape turing machine using single tape turing machine

I was going through the classic text "Introduction to Automata Theory, Languages, and Computation" by Jeffrey Ullman,John Hopcroft and Rajeev Motwani, where I came across the simulation of MULTI-TAPE ...
65 views

### Languages such that DFA requires $\Omega(c^k)$ states but NFA needs only $O(k)$ states?

Given an alphabet $\Sigma$, let $c=|\Sigma|$. Can a set of languages $\{L_k\}$ be created, such that any DFA for $L_k$ has $\Omega(c^k)$ states and a NFA for $L_k$ exists with $O(k)$ states? I'm ...
78 views

### The total length of input to a pushdown automata which accepts by empty stack is an upper bound on the number states and stack symbols

I was going through the classic text "Introduction to Automata Theory, Languages, and Computation" (3rd Edition) by Jeffrey Ullman ,John Hopcroft, Rajeev Motwani, where I came across few statements ...
734 views

### Convertion from NFA to DFA

I have converted nfa to dfa. But when I checked with some examples, it looks like it is wrong. ...
56 views

### Equivalence of states between two “quasi-deterministic” strongly connected Büchi automata accepting the same $\omega$-language

Hope someone can point me to the right direction to solve this problem. Premise. I call quasi-deterministic Büchi automaton (qDBA) a Büchi automaton $B = \langle S, \Sigma, S_0, \delta, F \rangle$, ...
47 views

### CFG for this language $\{a^k b^m c^n \mid 1 \leq k, m, n, n \leq 2k\}$ [duplicate]

I'm kinda new in this topic and I don't know how to figure out the rules to make a CFG out of this language, if anyone could give me an idea or hint so I can try to solve it knowing that, I would be ...
136 views

### Is there a difference between the equivalent automaton of a grammar and an automaton which accepts the language produced by the grammar?

I have been assigned some homework in uni, related to push-down automatons (evaluated via final state, not empty stack) and context-free grammars. I have noticed that questions related to generating ...
27 views

### How interpret the notation $f:\{0,\dots, N-1\} \rightarrow \{0,\dots, N-1\}$, $N$ is a number of the form $2^n$? [closed]

I need help how to interpret the following notation for $f$: Zeroes and ones form a binary number which can be converted to decimal notation. Thus, we may think of the computer as calculating a ...
3k views

### Why does a DFA have multiple final states?

I am taking a course on programming language design and we got to the DFA part. It is known to be formally defined by a 5-tupple but they did not make it very clear to us why a DFA can have multiple ...
Define language $L’$ for given regular language $L$ as: $$L’=\{uv | u,v\in\Sigma^{*}, vu\in L\}$$ is language $L’$ also regular? Hello, I need some help with solving this question. I need somehow to ...