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
2
votes
1answer
26 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
41 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
30 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
41 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 ...
0
votes
2answers
84 views

Find language and regular expression

I don't know how to find the Language and the regular expression for each one. there are any special method for those kind of question?
-4
votes
0answers
25 views

Implementation level description of Multi tape Turing Machine

Consider the language A = {0^k | k = n^2 for some n > 0}. Provide implementation level description of multi-tape TM M such that L(M) = A. I need answer on urgent basis I need it to help in solving ...
1
vote
1answer
93 views

Building non-deterministic automata

I'm trying to make non deterministic automata for specific language . I cant understand my mistake! Rules: 1){a,b,c} 2) if I have the sequence "bb" and later in the word I have the sequence &...
1
vote
1answer
46 views

Is there a pushdown automaton for $\Sigma^* \setminus \{ a^n b^n c^n \mid n \ge 0\}$?

According to this statement: Every regular language is context-free. Regular languages are closed under complement, so the complement of a regular language is regular. Consequently, any regular ...
0
votes
2answers
50 views

Myhill-Nerode equivalence classes

I need to find the Myhill-Nerode equivalence classes for the language $$ L = \Sigma^*\setminus \left( \{\epsilon, cc \} \cup \{ cca^i: i\geq 2 \} \right) $$ over $\Sigma = \{a, b, c \}$ I'm familiar ...
1
vote
1answer
28 views

What is the language of Sigma^n? Confused about meanining

I am learning the Theory of Computation, and I came across the language $\Sigma^n$. Could someone please explain what that could mean if $\Sigma$ is the alphabet? Thank you so much!
1
vote
1answer
30 views

Finding right quotient of $a^*b^*/b^*.$

I argue that right quotient of $a^*b^*/b^*$ is $a^*$,is that true?any help or argument to accept or reject my argument will be appreciated:)
2
votes
1answer
53 views

Minimal DFA accepting strings whose length is divisible by $x$ or $y$

Consider the language of all strings whose length is divisible by either $x$ or $y$, where $x,y \geq 1$. After trying various values of $x$ and $y$, I noticed made the following observation: If one ...
0
votes
0answers
30 views

data structure for string queries algorithm

We have a finite set of words $D$, and denote $Pref(D)$ to be the set of all prefixes from words in $D$ and $l(D)=max_{w\in{}D}|w|$ is the length of the longest word from $D$. Problem statement: Given:...
1
vote
2answers
88 views

Prove that following grammar is ambiguous; S → a | S + S | S S | S* | ( S )

Prove that the following grammar is ambiguous; S → a | S + S | S S | S* | ( S ) checking ambiguity in grammar. the subject of this question is compiler construction and automation. would you please ...
0
votes
1answer
47 views

Two way deterministic pushdown automaton accepting word consisting of two equal words

I have a homework where I have to construct two way deterministic pushdown automaton that accepts this language: {ww | w ∈ {a, b}*} Does anyone have any idea? Thanks a lot
4
votes
1answer
124 views

Kleene's Theorem and TMs

I wanted to know that based on Kleene's theorem (a language is regular iff some FSA recognizes it), does every regex have a TM (Turing machine) that halts on exactly the same language? Is this ...
1
vote
0answers
17 views

Configuration of a space bounded turing machine

A configuration of a Turing machine is defined as the following: an ordered triple $(x, q, k) ∈ Σ^* × K × N$, where $x$ denotes the string on the tape, $q$ denotes the machine's current state, and $k$...
0
votes
0answers
67 views

Create a turing machine for log base 2 of n

How would someone create a Turing machine that computes ⌈log2(n)⌉? I know that: n = 1, 2, 3, 4, 5, 6, 7, 8, ... f(n) = 0, 1, 2, 2, 3, 3, 3, 3, ... And that I want the input tape to have n 1's in it to ...
0
votes
0answers
24 views

Draw a CFG (context-free-grammar) that starts and ends with the same symbol yet has odd number of 1's

I figured out that the CFG that starts and ends with the same symbol in alphabet $\Sigma=\{0,1\}$ will be : S -> 0A0|1A1|0|1| A -> 0A|1A|𝜖 How can i interpret the odd number of 1's also?
3
votes
1answer
87 views

Deciding whether complement of context-free language is context-free

I need to find out if the following problem is decidable: Given a context-free language $L$, decide whether its complement $\bar{L}$ is also a context-free language. I am having trouble in defining ...
0
votes
0answers
4 views

How to map the tapes of a single tape Turing Machine into a “2-tape” Turing Machine which has only an initial state and an end state

so i am struggling with demonstrating that every single tape TM can be simulated by a 2 tape TM with only two states. I don't really understand how we can prof this with only 2 states.
0
votes
1answer
39 views

Cardinality of formal languages

Given the theorem: Let $\Sigma$ be an alphabet. The set $\mathcal{P} \left( \Sigma^{\star} \right) $ is uncountable. In other words, there are uncountably infinite languages over any alphabet. Can ...
0
votes
1answer
49 views

Create a PDA that accepts the following language

I need to create a PDA that accepts by empty stack and accepts the language formed by strings over the alphabet $\{a, b\}$ of the form: $uw$, where $w$ is the string $u$ reversed and doubled. So, for ...
1
vote
2answers
61 views

Proving some subsets of a regular languages to be regular languages

I have to prove that if a language $L$ is regular then: a) $NONPREFIX(L)=\{u \in L / $none of the prefixes (not $\epsilon$ or $u$) of $u$ are elements of $L \} $ is regular On this one I think I can ...
0
votes
1answer
58 views

{a^n b^n c^n | n>=1} - PDA

I just started learning context free grammar and Pushdown Automata, I tried implementing this particular language via a PDA, despite being told this language is context sensitive. How I attempted it ...
1
vote
1answer
19 views

is the intersection of a context free language and a regular language a two way street?

I wasn't sure how to word it correctly, hence the 'two way street' in the title. My question is: The intersection of a context-free language and a regular language always results in a context free ...
0
votes
0answers
63 views

Halting problem. Decider “recognising itself” in the input?

This is about the halting problem. My questions are: where do you think are logical flaws in what I am going to write? How do you think this does not invalidate the proof for the undecidability of the ...
0
votes
0answers
14 views

Having trouble understanding how to prove a language context free? [duplicate]

I've been studying the theory of automata. I came across this problem in the book and unable to understand how to solve this. I've solved some examples using the Pumping lemma but this one uses ...
1
vote
1answer
21 views

Can CFGs generate all languages? Are they (PDAs) finite or infinite state automata?

I was looking for the limitations of a CFG. I think there is some limitation given there are only finitely many states of a PDA (or non-terminals in a CFG). I suspect that languages like $\text{L} = \{...
1
vote
0answers
34 views

How to get a piece of the Pie? Theoretical Plate Stacking Problem

This is just a theoretical problem that I found in the wild and want to know your solution. A stack of plates is made between you a cousin and a few others. Every (4 to 7) many random hours the plate ...
1
vote
2answers
40 views

DFA to accept a String containing even number of both A and B, but rejects empty String

I want to draw a DFA to accept a String containing even number of both A and B, but rejects the empty String(ε) I have already drawn the DFA which accepts the above language, without rejecting the ...
1
vote
2answers
55 views

Is $L = \{ w : \#_a(w) = \#_b(w) \}$ regular?

Is $L = \{ w : \#_a(w) = \#_b(w) \}$ regular? I do not think it is. I recently posted a question and from there I was thinking if this language is regular. If we assume on the contrary, then there ...
-1
votes
1answer
30 views

What are the practical examples of Semidecidable problems? Is NP problem a semidecidable problem?

I am going through a Turing machine topic. I know about decidable, semi decidable, and decidable problems. But honestly speaking, I did not get any practical examples of Semidecidable problems. Can ...
3
votes
1answer
68 views

A language that is not context free

I working through some textbook exercises, and came across a problem that I'm struggling with. Give a CFL $L$ such that $\{x|\forall y \in \Sigma^* \space xy \in L\}$ is not a CFL. I've got the idea ...
0
votes
0answers
47 views

NFA recognizing strings in $\{0,1\}^*$ that have two zeros separated $4i$ characters, for some $i\geq1$

I am trying to design a nondeterministic finite automaton that recognizes the language of strings in $ \{0,1\}^{\ast}$ that have two zeros separated by a string of length 4i, for some $i \geq 1$. Let $...
2
votes
2answers
51 views

How to we prove if a right linear language is ambiguous?

Considering the following language as an example: $$\begin{align} S &\rightarrow aS \mid bA \\ A &\rightarrow bA \mid aB \mid aD \mid \varepsilon \\ B &\rightarrow aB \mid \varepsilon \\ D ...
2
votes
1answer
19 views

Measuring the difficulty of a sequence-to-sequence problem using automata theory

Automata theory measures the difficulty of language recognition problems by using an automaton that can accept or reject for the given string. However, I want to measure the difficulty of a sequence-...
0
votes
1answer
39 views

Does CSL contain an empty string or not? Is empty string accepted by LBA or not?

I am confused and got contradictory statements from various sources. It is mentioned in Page no 292, Chapter 11 A Hierarchy of Formal Languages & LBA, Peter Linz -An Introduction To Finite ...
1
vote
2answers
90 views

Why Linear bounded automata requires Nondeterministic Turing machine ? Why not Deterministic Turing machine?

Going through the topic of LBA, i.e., Linear bounded automata. I found that LBA requires the NTM with some constraints on tape. I found the same information from different sources. But I did not get ...
2
votes
3answers
45 views

How to use DFA/NFA to prove the language {$0^n 𝑥1^𝑛$ | x ∈ Σ*, n ≥ 1} is regular?

I'm trying to prove the language L = {$0^n 𝑥1^𝑛$ | x ∈ Σ*, n ≥ 1} is regular, but don't know how to present it in a DFA/NFA. I'm thinking to have n+1 states in a NFA, with the start state as the ...
5
votes
2answers
1k views

What are the options of head movement for a Turing machine?

I find several contradictory definitions regarding the head movements of the Turing machine. In some places, it is only L / R. While in some other formal definition; it is L / S / R. Which one is ...
0
votes
1answer
26 views

minimum number of states in cross product of two minimum DFAs

If FA1 and FA2 are 2 DFAs with minimum number of states. I want to find cross product DFA (FA1XFA2). Will the cross product DFA obtained from 2 minimum DFAs also have minimum number of states(num of ...
0
votes
1answer
42 views

Deterministic pushdown automata for the language $L=\{ a^ib^j| i \neq 2j+1, i,j>0\}$ where $\Sigma = \{a,b\}$

Does there exist a Deterministic pushdown automata for the language $L=\{ a^ib^j| i \neq 2j+1, i,j>0\}$ where $\Sigma = \{a,b\}$ I have tried to find a pushdown automata and it turned out to be a ...
-1
votes
1answer
26 views

Proving of regular language [duplicate]

Is this regular or not L = {w1w^R | w ∈ {0,1}* (where for any word w ∈ {0,1})*, w^R denotes the reverse of w)
6
votes
1answer
358 views

What are the closure properties of LL(k) languages?

Suppose I have two LL languages $L_1, L_2$, both describable by LL($k$) grammars for the same $k$, and regular language $R$. Which of the following are also LL languages, and can they be described by ...
1
vote
1answer
103 views

What does “lookahead” refer to?

I keep hearing about lookahead parsers, LL parsers, LR, LALR, etc... but no clear explanation behind the etymology of this word. What does "lookahead" refer to? How does this relate to LL, ...
1
vote
2answers
66 views

How to prove that concatenating a language A and A* is commutative?

Suppose we have a language $A$. I want to prove that $AA^*$ is commutative. I know that this expression equals $A^+$, but I'm not sure how to go about a proof yet. This is my attempt so far. If $A$ is ...
0
votes
0answers
47 views

How to show $L = \{0^{i}1^{i^{2}}| i \ge 0\}$ is not context-free using pumping lemma

I've been struggling with this problem for quite a while now and don't really understand what to do for the pumping lemma here. We have the language $L = \{0^{i}1^{i^{2}}| i \ge 0\}$ and we need to ...
0
votes
0answers
87 views

Generalization of automaton - Sipser example 1.33

I am trying to construct a nfa that generalizes Example 1.33 found in the book Introduction to the Theory of Computation by Sipser, but I am quite sure that my transition function is wrong. I'd like ...

1
2 3 4 5
29