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
16 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
11 views

NFA -> DFA subset construction worst case [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 Hopcroft et ...
1
vote
0answers
22 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. ...
-4
votes
0answers
17 views

Identities of Regular Expression [closed]

fill in the blanks of this table ? <body>
0
votes
1answer
32 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 $+$, $*...
-4
votes
0answers
41 views

How to remove epsilon production from this Context Free Grammar?

I want to remove the epsilon production from the following grammar: S → [ S ] | SS | ε
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
36 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
17 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
-2
votes
2answers
48 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
43 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 \...
1
vote
1answer
44 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$$
0
votes
1answer
20 views

Write the Context free Grammar

What will be the context-free grammar of $B= A_1.A_2 $ when $A_1 = \{0^n1^n|n\geq 0\}$ $A_2 = \{1^n0^n|n \geq 0\}$ Also verify using a string. if the Grammar for $A_1$: $S_1 \rightarrow 0S_11 | \...
2
votes
2answers
116 views

Is the union of computable enumerable sets computably enumerable

Let $\{A_n : n \in \mathbb{N}\}$ be a collection of c.e. (computably enumerable) sets. Is $\bigcup_n A_n$ c.e.? That is, is the union of c.e. sets c.e.? Otherwise, under what conditions will this be ...
-2
votes
0answers
36 views

NP as the set of polynomial verifier and set of decidable problem in nondeterministic polynomial time

My initial idea is to show that the equality of the sets by first proving (a) ==> P is subset of NP and secondly, (b) <== NP is subset of P?
-1
votes
1answer
53 views

Is this language a context free language?

Consider the following language, where the alphabet is $\{0, 1, 2\}$: $B = \{0^a1^b2^c|a, b, c \geq 0 \text{ and }c = ab + 1\}$. Is this language a context free language? Prove your answer. I am ...
3
votes
0answers
30 views

What's the difference between a Generalized Nondeterministic Finite Automaton (GNFA) and a Generalized Transition Graph (GTG)?

I've recently come across a few articles that talk about a "Generalized Transition Graph" (GTG), but I've never heard of such a thing before. This other answer to a similar question leads me ...
1
vote
2answers
43 views

PDA accepting all words not of the form $b^na^n$

I am studying Automata theory. DFAs and NFAs seem pretty straightforward to me, but I don't quite understand how to design push-down automata for context-free languages. If I have context-free ...
1
vote
1answer
50 views

Exclusion in a context-free language?

I am learning automata theory, and I am confused about this exercise: Give context free grammar to create the following language where the input alphabet is $\{a,b\}$ $L = \{w \text{ where }w\text{ ...
1
vote
1answer
34 views

Finite automaton whose alphabet is $\mathbb{N}$

Is it possible to have a finite automaton where $\Sigma = \mathbb{N}$? Why or why not? I think it is possible to have a set of all natural numbers, however I'm not sure why.
2
votes
1answer
62 views

Is $\{\varepsilon\}$ a conventional way to mark the empty language?

I am grading an exercise in Automata and Formal Languages and see many of the students use $\{\varepsilon\}$ as the empty language. At first I thought this was an error, and I have asked the lecturer ...
1
vote
1answer
44 views

Prove/Disprove: NP is closed under “mixed” complexity

Let $\displaystyle S_{1} ,S_{2} \subseteq \{0,1\}^{*}$, we say $\displaystyle x\in S_{1}°S_{2}$ if it's of the form $\displaystyle x=x_{1} x_{2} ...x_{n}$, for $\displaystyle n$ even, such that: $\...
3
votes
1answer
53 views

Why are regular tree languages closed under intersection, but deterministic context free languages are not closed under intersection?

I am looking for intuition here. Essentially, I understand that the set of parse trees from a context free grammar forms a regular tree language. I also understand that regular tree languages are ...
0
votes
1answer
35 views

Undecidability and Unrecognizability of Language with two Turing Machines

I've been working on undecidability proofs and I found this question in the practice problems for the textbook "An Introduction to Automata Theory." I know that we start by contradicting the ...
0
votes
0answers
40 views

Co-relating the direct algo for $\epsilon-NFA$ to $DFA$ with the chain : $\epsilon-NFA \rightarrow NFA \rightarrow DFA$

I was going through the text : Compilers: Principles, Techniques and Tools by Ullman et. al where I came across the following algorithm to convert an $\epsilon\text{-NFA}$ to $\text{DFA}$ ...
-3
votes
2answers
64 views

Prove that the language Cats-Vs-Dogs is undecidable

Define Σ = {a, b, c, . . . , z} be the set of letters in the English alphabet. Prove that the following language is undecidable: Cats-VS-Dogs = {(M) | Either “cats” ∈ L(M) or “dogs” ∈ L(M), but not ...
0
votes
1answer
29 views

Regular set of the “does not contain” kind

Given a language $L$ and a set of strings $\Sigma^* = \{0, 1\}^*$, how can I find a regular set that expresses $L = \{ w \in \Sigma^* \mid w$ ends with $00$ and does not contain $11\}$? Well, the part ...
-1
votes
1answer
27 views

Regular expression for the language $\{wtw^r \mid w, t \in\{0 \cup 1\}^+\}$

What is a regular expression for the language $C=\{wtw^r \mid w, t \in \{0 \cup 1\}^+\}$? Here $w^r$ is the reverse of $w$.
0
votes
1answer
45 views

Prove no DFA with four states can accept L={111}

Assume we have a language L={111}. Prove no DFA with four states can accept L. Can’t a DFA with 4 states accept L?
1
vote
1answer
50 views

Finite automaton for all words whose length $n$ satisfies $\operatorname{gcd}(n,504) \geq 6$

I have been working on the following homework question, and I just can't seem to make any progress: Construct a finite automaton having fewer than 36 states that recognizes the language $\{s \in a^* :...
0
votes
1answer
35 views

Deteremine if Language is in $R$ or $RE$

$$L =\left \{ \langle M \rangle \mid \exists x\in \Sigma^* \left(\left | x \right |\leq 10000 \wedge H(M, x\right) \right \}$$ Where $H(M, x)$ denotes whether Turing machine $M$ halts on input $x$. My ...
-1
votes
2answers
58 views

DFA for $\{0^m1^n \mid m+n \text{ is even}\}$

How do I construct a DFA for the language $\{0^m1^n \mid m+n \text{ is even}\}$? The corresponding regular expression is $(00)^*(11)^* + (00)^*0(11)^*1$.
2
votes
0answers
38 views

Whether there exists a probabilistic automaton satisfying $\Pr \{ x \in L\}=\frac{\Pr \{ x \in L_1\}}{\Pr \{ x \in L_1\}+\Pr \{ x \in L_2\}}$

Suppose that there are two probabilistic automata $A_1$ and $A_2$ with a same finite alphabet $\Sigma$. The languages of them are $\mathcal{L}_{1} \subseteq \Sigma^*$ and $\mathcal{L}_{2} \subseteq \...
1
vote
1answer
60 views

How to prove a language isn't necessarily regular? [duplicate]

Assuming we have a regular language $L$, how can we prove that $L'= \{ xz \mid \exists y : xyz \in L \text{ and } |x|=|y|=|z|\}$ isn't necessarily regular. So far I can't come up with much for how to ...
1
vote
1answer
31 views

Reduce PDA for a given language

I drew a Push-down Automata, accepting the following language: $$ \{ xcy : x,y \in (a+b)^*, \#_a(x) > \#_{bb}(y) \}. $$ Here $\#_{bb}(y)$ counts the number of times that $bb$ appears in $y$, with ...
1
vote
1answer
47 views

Computing $(a+b)^*c^*(a+b)^* \cap (b+c)^*a^*(b+c)^*$

how can I find the regular expression for this intersection ? I've tried to find words but it did not help too much.. $$[\; (a+b)^* c^* (a+b)^* \;] \cap [\; (c+b)^* a^* (c+b)^*\;]$$
1
vote
1answer
35 views

Intuition for irregular languages

I'm struggling in understanding how to recognize irregular languages. I know what the meaning of irregular language but still find it hard to recognize. Are there any tips to recognize better and to ...
1
vote
1answer
32 views

All strings in which every substring 000 appears after every 1

I found this given problem as follows: Write a regular expression where all strings in which every substring 000 appears after every 1. Now, I also found the answer from Illinois university study ...
0
votes
0answers
25 views

Finite automaton for $\{0^{2n} : n \ge 0 \} \cup \{(100)^m : m \ge 0\}$ [duplicate]

I have to construct an FA for the following language: $$ \{ w_1,w_2 \in \{a,b\}^* \mid w_1 = 0^{2n}, w_2 = (100)^m, \text{ for some } n,m \in \mathbb{N} \}. $$ Does anyone here have any experience ...
0
votes
1answer
42 views

Computing FOLLOW sets of left recursive grammar

Left recursive ambiguous expression Grammar: $E \rightarrow E+E \mid E*E \mid (E) \mid \mathbf i\mathbf d$ I tried computing FIRST and FOLLOW sets of both left recursive grammar and after ...
0
votes
2answers
87 views

Why do register machines outperform stack machines?

Wikipedia says stack machine “designs have though been routinely outperformed by the traditional register machine systems, and have remained a niche player in the market.” Why is this?
0
votes
0answers
33 views

On the queue automaton and acceptance of this language

We have this language: $$ L = \{𝑥𝑥^r|𝑥∈Σ^∗\} $$ We want to show that it can be accepted by QA. consider a letter like #, before anything we push it to the queue. using this additional letter, we ...
2
votes
1answer
58 views

this language and acceptance by queue automaton

I don't know how to prove or show that: $ L_1 = \{xx|x \in \Sigma^\ast\} $ (that can be accepted by queue automaton) If it would be possible, show by deterministic queue automaton, if not, by non-...
2
votes
1answer
28 views

Unique decipherability of infinite regular language

Can we design an algorithm to test if a infinite regular language is a code? We have the S-P algorithm to determinate if a finite language is a code. But how about the infinite part of regular ...
0
votes
0answers
16 views

Check if the regular expression r made up of the single symbol alphabet Σ = {a} defines language L(r) = a* [duplicate]

I have got to write an algorithm programatically using haskell. The program takes a regular expression $r$ made up of the unary alphabet $ \Sigma = \{ a \} $ and check if the regular expression $r$ ...
1
vote
1answer
46 views

Find a linear bounded automaton that accepts the language $L = \{ a^{n!} : n \geq 0 \}$

I need to construct linear bounded automaton for the language $L = \{ a^{n!} : n \geq 0 \}$. I know how LBA functions, however, I don't have a thought how it can check the n! that to in the power of a....
1
vote
1answer
35 views

State complexity of difference of two languages

Given $A_1$ - DFA with $n$ states, $A_2$ - NFA with $m$ states (both over the same alphabet - $\Sigma$). What's the state complexity, i.e. an upper bound for the amount of states of the minimal DFA, ...
1
vote
1answer
53 views

What is the theoretical minimum number of “switches” requried to implement a Turing-complete CPU?

Where "switches" are the basic abstract building blocks for logic gates: vacuum tubes, transistors, magnetic relays, or whatever. We're not counting any switches in the RAM or tape drive ...

1
2 3 4 5
30