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,564
questions
0
votes
1answer
37 views
How to design PDA for this language?
I'm having a hard time trying to build the PDA for this language:
$$L=\{a^nb^m: n,m \geq 1 \land m=4n+2\}$$
I don't know how many $a's$ should I push into the stack when reading $a$, and how many $a's$...
-3
votes
1answer
51 views
Design an NFA to recognize the given language. (Table and diagram) [closed]
Construct an NFA over {a, b} that accept strings
having aa as substring.
Construct an NFA over {0,1,} that contain 0110
or 1001.
Construct an NFA over {a, b} that accept strings
starting with a ending ...
0
votes
3answers
203 views
How it's possible decide CNF by having a turing machine that decide SAT?
Suppose we have a Turing machine $M$ as black box that decide $SAT$ problem. Now suppse we have a $CNF$ formula $\phi$ with $n$ variables. How it possible checking satisfiblity of $\phi$ and then ...
-3
votes
0answers
10 views
Finding out the language generated by a context-free grammar
how can i find out the language that accepted by this cfg :
S -> A B | B C
A -> B A | x
B -> C C | y
C -> A D | x
D -> y
1
vote
0answers
53 views
Is there a complexity measure on regular grammars connected to the descriptional complexity of the DFAs?
This question is directed at DFAs/NFAs and regular languages and regular grammars.
Define the "descriptional complexity" of a language as the size complexity of the family of DFAs that ...
0
votes
0answers
29 views
How do right contexts work in context-sensitive L-Systems?
I am working on an implementation of context-sensitive 2-L systems as described in The Algorithmic Beauty of Plants by Aristid Lindenmayer, and am in need of clarification regarding context matching ...
0
votes
2answers
52 views
Equivalence relation between two CFG's
In our course: Automata and Computation there is a definition about Context-Free Grammars which states:
"Two CFG's $CFG_{1}$ and $CFG_{2}$ are equivalent if $L_{CFG_{1}} = L_{CFG_{2}}$ where $L_{...
2
votes
1answer
34 views
What does $g \to \lambda$ mean in the L-System for the dragon curve?
I am playing with L-System using the wonderful tool jflap. Below is the L-System for the dragon curve in the "JFLAP book: JFLAP – An Interactive Formal ...
0
votes
1answer
26 views
Can any language be expressed by regular expression?
I'm studying Autoamta Theory currently and am wondering if any Language (for example Lanugage L in Alphabet A={a,b}) can be expressed by regular expression.
In my current understanding the rule is &...
-1
votes
0answers
25 views
Say what language is generated by the context-free grammar
In each case below, say what language (a subset of {a, b}∗) is generated by the context-free grammar with the indicated productions.
S→ aSa | bSb | aAb | bAa
A → aAa | bAb | a | b | Λ
I tried to solve ...
3
votes
1answer
54 views
Is this language $X = \{x:xxx\in L\}$ regular?
I came across this question in my Theory of Computation class recently:
Consider a regular language $L$, and define $X = \{x:xxx\in L\}$. Is this language regular?
I believe that it is regular, and ...
-1
votes
0answers
16 views
Group input string by 4 characters by adding " " with a Turing Machine
I have this problem, where I have an input where:
alphabet of the input string is Σ = {a,b,c}
need to add a " " after every 4 characters.
Example: Input = "aabacc", Output = &...
0
votes
0answers
34 views
Show that if $A$ and $B$ are recognizable subsets of $\Sigma^*$ then so is $A \cup B$, $A \cap B$ and also $\Sigma^* - A$
I am working through a chapter of a book by Samuel Eilenberg about Automata, Languages and Machines as part of an university course in computer science.
And as an exercise in this chapter I have to ...
-1
votes
0answers
21 views
NFA-$\epsilon$ for $a.(a+b)^*.b.b$
The difference between these is $\epsilon$ during concatenation. I think the second one is correct. But I am confused because first one is shown in my textbook. I think both mean same but I am not ...
-2
votes
1answer
29 views
What does DFA that accepts at least 1 a or at least 1 b mean?
What are the language accepted by this DFA?
The truth table of OR-:
But I am unable to deduct what this dfa will accept?
Say-:
P=at least 1 a
Q=at least 1 b
So DFA should accept both ab. Or in ...
3
votes
2answers
563 views
Regular Expressions - What is difference between a+ and a⁺
I'm very confused as to if a+ and a⁺ mean the same thing or are completely different.
0
votes
1answer
49 views
Prove that $\{xyz \mid zyx \in A \}$ is regular if $A$ is regular
Does the following work and is there anything possibly simpler?
Let $X = (Q, \Sigma, \delta, s, F)$ be a DFA for $A$.
Intuitively, we want to "remember" (or guess) two states $p$ and $q$ ...
0
votes
0answers
39 views
conversion of regular expression to automata
I've a task to specify a finite automata (of any kind) that accepts the language described by this regular expression: $a(bab)^+b^*|(ab)^*(aa)^+$
My first solution looks like this:
I would like to ...
0
votes
0answers
27 views
conversion of epsilon NFA to NFA
I was given below task:
Eliminate Epsilon-transitions in below automata
My solution:
Is it correct that stage 1 is actually one of the final stages?
How does it work in given example? We have ...
1
vote
1answer
31 views
conversion of NFA to DFA (omitted states)
I've been given following task:
Determine the following nondeterministic automaton (omit unreachable states, if they appear during construction)
My solution to this:
Would like to ask for a ...
0
votes
1answer
13 views
Problems with simulating NFA with DFA
I have this NFA:
I want to simulate it with a DFA, thus I have the states {1}, {2}, {3}, {1,2}, {1,3}, {2,3} and {1,2,3}. Usually I look at every state and find out in which state I could end up when ...
1
vote
1answer
44 views
How to write a non-ambiguous grammar for the syntax of lambda calculus?
I tried to write a non-ambiguous grammar for lambda calculus, but it does not really work. The recursive-descent parser is easy to write though. I googled but all results I collected so far are ...
0
votes
1answer
43 views
Need help with constructing a DFA
I am trying to construct the DFA that accepts the following language
$$ L_2 := \left\{ w \in \{a,b\}^* \mid \#a(w) \text{ is divisible by } 3 \text{ and } \texttt{babbab} \text{is a substring of } w \...
1
vote
1answer
25 views
What is the difference between these 2 dfas for binary strings ending with 00?
The first one is from unreputed youtuber whereas second one is from reputed university called adiuni course of theory of computation.
Now I know what that second figure means, it means it also accepts ...
0
votes
2answers
31 views
What is "function of size of input"?
Context-:
Problems that can be solved by a computer using no more time than slowly growing function of size of input are called tractable. Polynomial functions are slowly growing functions. Functions ...
2
votes
1answer
117 views
How to verify-: A language over Σ is also a language over any alphabet that is a superset of Σ?
Context-:
A language over Σ need not include strings with all symbols of Σ Thus, a language over Σ is also a language over any alphabet that is a superset of Σ.
https://www.univ-orleans.fr/lifo/...
1
vote
0answers
26 views
Which is the best theory of computation/automata/formal language book for practice problems(unsolved)? [closed]
I have
Introduction to automata theory, languages and computation by hopcroft, rajeev motwani, jeffrey d ullman
Elements of the theory of computation HR lewis Christos H papadimitriou
Theory of ...
1
vote
1answer
32 views
Constructing PDA for $L = \{w\in\{a,b\}^{\ast}\;|\; |w|_a > 2|w|_b\}$
Construct a PDA, which recognizes the following language $L$: $L = \{w\;|\; |w|_a > 2|w|_b\}$, so it is the language that consists of words which have more than twice as many $a$'s as $b$'s.
I ...
-1
votes
1answer
48 views
Design a DFA that accepts numbers whose sum of digits is $2 \mod 3$
Design a DFA that accepts language $$L = \left\{ x \in \{ 0, 1, 2 \} : \text{ sum of digits in } x \text{ is } 2 \mod 3 \right\}$$
How to make a DFA for this? I have no idea how to solve this dfa ...
0
votes
1answer
46 views
DFA for even number of 1's
My attempt at solution-:
Solution by a teacher-:
Both are giving same answer, is the one that I made correct?
0
votes
1answer
40 views
Prove the class of regular languages is closed or not closed under the operations below
Suppose $A$ and $B$ are both languages over $\Sigma=\{0,1\}$. We use $n_0(x)$ and $n_1(x)$ to represent the number of $0$s and $1$s in the string $x$ respectively. Consider the following two ...
0
votes
0answers
111 views
Turing Machine for Check Validity of Unary Multiplication (A=B*C)
I have a lot of difficulty with the turing machines. I understand the theory well, but I need help with a lab exercise...
Design a SINGLE TAPE Turing Machine that accepts the language $a =
> b \...
0
votes
0answers
31 views
Why linear bounded automata emptiness and finiteness isn't decidable? [duplicate]
We know that linear bounded automata has tape size based on input size which is limited. Context-sensitive languages are accepted by LBA. My question is that if LBA has limited tape size why it's ...
0
votes
1answer
40 views
Difference between Counter-machine and stack machine
I read from this question that counter automata is a push down automata with only one symbol allowed on the stack (plus a fixed bottom symbol).
My question is counter machine means counter coexist ...
0
votes
0answers
11 views
Construct Deterministic Accepter for binary string containing at any position
do you have any idea of designing a deterministic accepter where the set of all these binary strings contains at any position? The string is: 0100101
So, the accepted input could be: 0100101 or ...
0
votes
0answers
12 views
Need literature on First order logic definibility through Automata
Actually I am in search of some good literature on defining First order logic through Automata. It will be very helpful if someone can give me some links.
0
votes
0answers
67 views
My proof for equivalence of DFA and NFA
I came up with this proof for the following theorem:
If $L$ is a language produced by an nfa, then there exists a dfa $M$ where $L(M) = L$.
Is it correct? If it's not, what are the flaws of my proof,...
1
vote
0answers
25 views
Handling infinite loop in implementation Pushdown Automaton (PDA)
I've got a basic implementation of a Pushdown Automaton which recursively checks the rules of a grammar in CNF to find whether a given input string is accepted or not, and it can also count the number ...
0
votes
0answers
51 views
Efficient Turing machine to check that an unary multiplication is valid
I'm trying to find an efficient one-tape Turing machine that accepts inputs in the form R=A*B iff the equation is indeed true. All three numbers are written in ...
2
votes
1answer
30 views
How can I represent this description in set builder notation?
The language that accepts strings with the number of 0s being congruent with 1%3 and an even number of 1s over the alphabet {0, 1}.
1
vote
1answer
23 views
Correct complement of a regular language when the union of the languages do not lead to entire set of strings over the given alphabet?
I have a question that says that the complement of a regular language given as:
$L_1=\{a^nb^m|(n+m)<5\}$ is $L_2=\{a^nb^m|(n+m)\geq5\}$ over $\Sigma=\{a,b\}$, and therefore, we can simply construct ...
1
vote
1answer
30 views
Designing a NFA that accept the set of strings that contain an even number of substrings 01
I'm new in theory of computation. Here {0,1} set of input symbols. I tried to make the NFA from L(M)= set of all accepted strings, but unable to complete it. Can someone give some hints that how ...
4
votes
2answers
74 views
Is the language "substrings of a regular language that are over half the length of the superstring" regular?
We say $x$ is a majority substring of $y$ if $y \in \Sigma^* x \Sigma^*$ and $|x| \geq \frac 12|y|$. If $B$ is a regular language, is the set of majority substrings of $B$ regular?
I was provided the ...
1
vote
1answer
28 views
Counter automata with a bound on the counters?
It is widely known that emptiness of counter automata is undecidable since two counters are enough to simulate a Turing machine (see the classic book from Hopcroft and Ullman, for example).
However, ...
20
votes
9answers
4k views
Would it be wrong to say that the processor (and hardware) is the implementation of an interpreter for machine language?
The question is basically in the title. I know that a computers hardware is of course some physical object, where as the interpreter is some abstract thing that does something abstract with the code ...
0
votes
1answer
96 views
What is the meaning of the pipe symbol here?
I am reading Distributed Algorithms by Nancy Lynch. In chapter 16, I came across the pipe symbol. Does this mean the same as "or" in some programming languages or could someone explain that ...
3
votes
1answer
69 views
Can a non deterministic finite automaton go into infinite loop?
Here is the exact same question but on deterministic finite automaton. The case for deterministic finite automaton is simple. For each state only one transition is possible for each input symbol and ...
0
votes
0answers
62 views
Regular language closed under homomorphism
I am trying to solve problems from the textbook 'Introduction to the Theory of Computation' by Micheal Sisper, 3rd edition.
I am attempting to show various properties of regular languages and their ...
0
votes
1answer
24 views
Mapping reduction properties exercise
I am having trouble understanding how to conclude if the statements are true or false, I would really appreciate your help.
We know about three languages, A, B and C.
There exists a mapping reduction ...
1
vote
1answer
32 views
Find a transducer that maps a given deterministic process to another
Let $S$ denote a deterministic process which generates a certain string, described through a Hidden Markov Model. More specifically, for a process with alphabet $\mathcal{A}$ and $n$ hidden states, ...
