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