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
1answer
22 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 ...
0
votes
0answers
15 views

Maximal acyclic DFA? [closed]

Given an alphabet $\{0,1\}$ and $n \in \mathbb{N}$, how would one go about constructing a minimal acyclic deterministic finite state automaton with the maximum number of states over all the strings $(...
0
votes
0answers
16 views

Whether there exists a Deterministic Infinite Automata (DIA), which accepts all strings in L and rejects all stings not in L?

Given an automata DIA I = (Q,Σ,δ,q0,F), and the set of states Q is infinite. The set of characters Σ is still finite. Wondering whether there is an I and an arbitrary language L over Σ, such that I ...
0
votes
0answers
22 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 ...
-8
votes
0answers
31 views

Construct PDA for language

I want to construct a pushdown automaton for the language: wqw^-1 over the alphabet {0,1} for which => number of 0's in 'q' = 2 * number of 1's in 'q' + 1 what ...
-2
votes
0answers
9 views

Am I missing anything? (Theory of Computation: CFG to CNF)

Convert the following grammar to Chomsky normal form. S → ASA | A | ε A → aa | ε I got: S -> S | QA |AA | AS | SA| XX S -> QA | AA | AS | SA | XX A -> XX X -> a Q -> AS
3
votes
0answers
27 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 ...
0
votes
1answer
29 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
29 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
29 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
20 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
23 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
16 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
0answers
12 views

What would be an accepting sequence of configurations for this PDA?

What would be an accepting sequence of configurations for this PDA? I'm not sure how to approach this question, unless it's just trial and error?
-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
22 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
34 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
26 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
23 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 ...
-1
votes
1answer
34 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
20 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
50 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
39 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
36 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 ...
-6
votes
0answers
100 views

PDA and context-free languages

How can we prove that: Class of linear bounded PDA languages ∼ Class of CFLs I know that for a linear bounded PDA there is a constant $k$ such that the stack size for $w$ is at most $k|w|$. I also ...
1
vote
0answers
23 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
37 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
46 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
39 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
21 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
-1
votes
2answers
57 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
44 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
52 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
126 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 ...
-1
votes
1answer
54 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
34 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
48 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
53 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
35 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
63 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
46 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
55 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
36 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
41 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}$ ...

1
2 3 4 5
30