People who code: we want your input. Take the Survey

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
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$$

1
2 3 4 5
31