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
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, ...

1
2 3 4 5
32