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,217
questions
0
votes
0answers
8 views
Why is it not possible to prove the equivalence of nondeterministic and deterministic Turing Machines the same way as for NFAs and DFAs?
I found en excercise asking this question.
I know that for proving the equivalence between NFAs and DFAs we can use the conversion through subsets, and that for proving the equivalence between ...
0
votes
0answers
7 views
Is there a universal Turing machine for non-deterministic Turing machines?
I'm studying Formal Languages and Automata Theory and I found this question. I'm not sure of knowing the answer, so I'm asking for your help.
I know that a universal Turing machine can emulate any ...
-4
votes
1answer
19 views
DFA detterministic finite automata [on hold]
construct a DFA which accepts a divisible by 3 and b should also be divisible by 3
-1
votes
0answers
18 views
Design a DFA to output Decimal Number
An input alphabet consists of the following symbols ONE, TWO, THREE,....,HUNDRED. Design a DFA that accepts input as the English language representation (e.g., ONE HUNDRED THIRTY FIVE) of any number ...
-1
votes
0answers
16 views
Prove which languages are Recursive [on hold]
Consider the following languages.
L1={ ⟨M⟩ ∣ M takes at least 1000 steps on some input},
L2={ ⟨M⟩ ∣ M takes at least 1000 steps on all inputs} and
L3={ ⟨M⟩ ∣ M accepts ϵ},
(ϵ = Null String)
Where ...
0
votes
1answer
13 views
Lexicographic Order of Expression [Automata Theory]
what will be kleene star "expansion" of expression $a^*b^*$ in lexicographic order?
I'm confused and I really want to clear my concepts so I can proceed further
2
votes
1answer
40 views
Prove: If finite automata M with k states accepts a string with at least k characters, then the language L(M) is infinite
I need to prove that if finite automata $M$ with $k$ states accepts a string with at least $k$ characters, then the language $L(M)$ is infinite. I have no idea where to start. Any suggestions?
1
vote
1answer
30 views
How to propose a method to construct an automaton?
Given $0 \leq m < k$ and $p \geq 2$ it's defined $$A_{k,m,p} = \{ \alpha \in \{0,1,\dots,p-1\}^* | \alpha \text{ is a p-ary representation of } x \backepsilon x \text{ mod } k = m \}$$
It is ...
-1
votes
0answers
15 views
L' = { w | ww ∈ L where L is regular } [duplicate]
Let L be a regular language. We define another language
L' = {w | ww ∈ L} . Show that L' is regular.
I was trying to construct an automaton for L' but unable to construct it. Please help or please ...
0
votes
0answers
21 views
Uncommon case in Arden's lemma $q_{2} = 1q_{2} \cup 0q_{2}$
I'm trying to get the regular expression of an automata but an state has a form that I don't know how to solve, the form on its simplest example is:
$$q_{2} = 1q_{2} \cup 0q_{2}$$
What's the ...
0
votes
0answers
31 views
If $L^2$ is regular. Does that imply L is regular [duplicate]
If $L^2$ is regular. Does that imply L is regular.
I think L need not be regular. But I can't find any example where L is not regular but $L^2$ is regular.
My teacher told me an example where L={$0^...
1
vote
1answer
60 views
On $L^* - \{\epsilon\} = L^+$
$\Sigma^* - \{\epsilon\} = \Sigma^+$
$L^* - \{\epsilon\} = L^+$
Which of the above is always true?
I was following a discussion on a site and I came across this question. Some fellow ...
-1
votes
0answers
29 views
DPDA for $\{a^mb^nc^n \mid n,m \ge 1\}$?
How do I create a DPDA for $\{a^mb^nc^n \mid n,m \ge 1\}$?
I have found a solution for the similar language $\{a^nb^nc^m \mid n,m \ge 1\}$ but I am not sure, if the same reasoning applies to the DPDA ...
1
vote
1answer
33 views
Equivalence of different automata
I have a question about the equivalence of different automata. I looked up the similiar questions but sadly none of them are exactly, what I need or am looking for.
I know some of these are ...
0
votes
0answers
11 views
Guards on Transition and Deterministic versus Determinate State Machine
I am reading a passage from the book Introduction To Embedded Systems, A Cyber-Physical Systems Approach, by Edward Ashford Lee & Sanjit Arunkumar Seshia and I cannot understand a pharagraph:
...
0
votes
1answer
32 views
Number of Configurations of LBA(Linear Bounded Automaton)
The lemma is:
Let $M$ be an LBA with $q$ states and $g$ symbols in the tape alphabet.
There are exactly $qng^n$ distinct configurations of $M$ for a tape of
length $n$.
I want know why LBA has ...
0
votes
0answers
26 views
Computational power of machine learning
In a nut shell, machine learning is a class of algorithms that can "train" data-structures.
You provide a trainer with partial information, and it will produce some entity which can
be queried on ...
0
votes
1answer
36 views
Create automata from non regular grammar
I have two grammars:
L → ε | aLcLc
L → ε | aLcLc | LL
This two grammars are equals but the first one is regular, so it produces a regular language and a ...
0
votes
0answers
46 views
How to prove this language is not regular?
I am currently learning Pumping Lemma and found this question. But I am not able to prove it not regular. L = { $0^n$ | n is power of 2}. So, here I considered w = $0^{2^n}$ where n is constant of ...
1
vote
0answers
28 views
What is the class of automata with stack and unlimited amount of memory, addressable only by immediates?
Let's assume we've got an automata with infinite stack ($s_n \epsilon \mathbb{Z}$) and infinite amount of "registers", but no arbitrary memory access whatsoever and it's data is separated from code.
...
0
votes
1answer
23 views
Finite Language Closure Properties
Let L={F| F is a finite language over Σ}
which of the following operation is not closed for L?
a. intersection
b. union
c. complement
d. none of the above
I thought the ans as d as all finite ...
1
vote
0answers
46 views
Is there a metric or distance of two languages?
Given a language $L$, I am finding a method to evaluate the advantage of an automaton to decide $L$.
My goal is to decide a language $L$ (and maybe it is not decidable for automata). If one ...
1
vote
1answer
64 views
Determining equivalence classes of $\{w \in \{0,1\}^*\mid$ the $k$-bit of $w$ from the right is 1$\}$
I want to formally write the equivalence classes of the following language:
$$L_k = \{w \in \{0,1\}^*\mid\text{ the } k\text{-th bit of }w\text{ from the right is } 1\}$$
I understand the definition ...
0
votes
0answers
36 views
Testing if a state is in final state
Please excuse my language, I am new to the topic.
I am trying to classify/find a class of game that describes games such as chess, tic-tac-toe as a finite state machine.
For those games, final ...
0
votes
0answers
26 views
why does the pumping lemma want us to only consider the first repitition of states?
In Sipser's Intro to Theory and computation, He writes:
I don't understand the constraint on x. Shouldn't it be just y <=p? (Equal bc in the case when machine M runs through all states p) Making ...
2
votes
1answer
27 views
Pumping Lemma for Regular Languages with 3 variables (a^nb^mc^m)
I've been trying to understand the pumping lemma, and how to apply it to a language such as a^nb^mc^m where n >= 0 and m >= 0. The pumping lemma states that:
For any regular language L, there exists ...
0
votes
0answers
25 views
Is this language Deterministic?
I came across this question in Peter-Linz today,
Is the language L= { a^nb^n : n>=1 } U {b} deterministic ?
My doubt is that say we have a case like this {a^5 b^6} U {b}, after popping 5 a's from the ...
1
vote
1answer
51 views
How to characterize equivalence classes induced by Myhill-Nerode theorem?
Given $L=\lbrace w\in \lbrace 0,1 \rbrace^\ast : N_0(w)=N_1(w) \rbrace$, where $N_0(\cdot)$ and $N_1(\cdot)$ mean the number of zeroes and ones respectively, I need to characterize the classes ...
0
votes
1answer
43 views
find derivation trees for CFG
I need to draw the derivation tree for $1-2-(3-4)*5*6$ from the grammar below.
I want to know how many possible derivation trees are there from this grammar.
$$\begin{align}V_n&=\{expr,term,...
1
vote
1answer
66 views
Can CYK Parsing algorithm generate the parsing tree in O(n^3)?
I found this question What is the usage of CYK algorithm in the real world considering we have algorithms with a much better Time complexity? saying CYK Parsing algorithm can compute any Context Free ...
0
votes
1answer
29 views
Language which is recursively enumerable but not recursive [duplicate]
Can someone provide me with some examples of languages which are recursively enumerable but are not recursive. I know that there exist some languages which are not Recursive but recursively enumerable ...
0
votes
0answers
29 views
Does SLR(0), LALR(0) exists?
I read about LL(1), LR(0), SLR(1) and LALR(1) in many online sources and even in dragon book. However I found that no one talks about LL(0), SLR(0) and LALR(0). So I googled and come up against these ...
0
votes
1answer
21 views
Getting from one language to the other using closure properties(automata) [duplicate]
I am trying to deduct how i can, using closure properties, deduct that since the following language is not context free $$L=\left\{abc^{i_1}bc^{i_2}...bc^{i_{2m}}def^{j_1}ef^{j_2}..ef^{j_{2n}}ghq^{k_1}...
2
votes
2answers
71 views
Using pumping lemma to show a language is not context free(Complicated)
How can i show that the following long language is not context free using the pumping lemma?
$L=\left\{abc^{i_1}bc^{i_2}...bc^{i_{2m}}def^{j_1}ef^{j_2}..ef^{j_{2n}}ghq^{k_1}hq^{k_2}...hq^{k_o}\right\}...
0
votes
1answer
35 views
Construct NPDA for the language
$L=\{w \mid w \in \{a,b\}^*$, $\text{the number of a's is at least the number of b's} \}$
I'm stuck trying to build an NPDA that accepts $L$.
2
votes
2answers
31 views
Given an non-deterministic finite automaton, will its determinization always have unreachable states?
Given an NFA that accepts the regular language L, will its equivalent DFA which accepts the same language L always have unreachable states.
If it does, why?
0
votes
1answer
23 views
Counting number of states from a regular expression
Given the regular expression: $r=ab+((a+\epsilon)c^*)^*$.
Let A be a non-deterministic automaton that accepts the language of r.
How many states are in A?
Answer the question without building A ...
0
votes
1answer
27 views
How making non LL, non LR grammar a valid LL grammar, also makes it a valid LR grammar? Is there any connection between LL and LR conflicts?
I might unncecessarily overthinking here, but I had this weird possibly meaning less doubt:
When grammar is neither LL nor LR, it means, both LL and LR parsing tables involve conflicts. LL parsing ...
1
vote
1answer
114 views
what is the difference between transition function (delta) and extended transition function (delta cap ) in finite automata
my doubt is
what is the difference between transition function (delta) and extended transition function (delta cap ) in finite automata ?
both of them when started at a state q for a string w will ...
3
votes
1answer
36 views
Are the languages recognized by deterministic one-counter machines equivalent to deterministic context free language?
In Introduction to Automata Theory, Languages, and Computation, John Hopcroft mentioned[1]
In fact, a PDA In fact the languages of one counter machines are accepted by deterministic PDA's although ...
0
votes
1answer
24 views
Prove that the language L = {w1, w1w2, w1w2w3, ..} is regular, provided wi is in a regular language
Let's assume that we're working over a finite alphabet $\Sigma=\{a, b\}$. How can one prove that $$L_2=\{w_1w_2...w_m| m ∈ \mathbb{N}, ∀i(w_i ∈ L)\}$$ is a regular language, provided that L is regular?...
2
votes
0answers
76 views
Intersection of two deterministic parity automata
Given two deterministic parity automata $A_1=(Q_1,\Sigma,\delta,q_{01},c_1)$ and $A_2=(Q_2,\Sigma,\delta,q_{02},c_2)$ with the finite set of states $Q_i$, the finite alphabet $\Sigma_i$, the ...
2
votes
1answer
21 views
Help with figuring out if MAX(L) is a CF language
We call the word $x_1$ a true prefix of the word $x$, if a non-empty word $x_2$ exists so that $x=x_1x_2$. For the language L (over some finite $abc$..). We define MAX(L) as:
$MAX(L)$ = {$w_1 \in L $|...
1
vote
1answer
53 views
Can the difference of a non-regular and a regular language be regular?
I have some trouble understanding some exercises related to operations on regular languages.I tried to apply their closure properties, but I am not sure how to do the following exercises:
If $L_2,L_3$...
2
votes
2answers
53 views
Is the language L = {(a,b)* | #a * #b is an odd number} regular?
Is the following language regular? $$\{ w \in \{a, b\}^* |\ \text{the product of the number of $a$'s and the number of $b$'s is an odd number}\} $$
If i'm not mistaken the condition is the same as ...
2
votes
1answer
44 views
Construct a DFA from the regular expression (a)*+(aab)*
I've broken down the expression into two simpler DFAs but right now I'm stuck.
I don't know what to do with the expression a*, my solution currently (as presented above) is a NFA, not DFA.
2
votes
1answer
20 views
Proving a language comprised of 2 languages is regular(with suffix and prefix)
I am having hard time proving that the following language,comprised from two regular languages $L_1,L_2$(over the same $\Sigma$)is indeed regular:
$$L^\frown = \{ w\in \Sigma^* | w=u\sigma_1\mu_1...\...
4
votes
1answer
26 views
Proving a language comprised of 2 languages is regular
So glad to find this place. I have been struggling for quite a while with this given question and i am not sure how to fully address it.
The question:
$L_1$ and $L_2$ are regular languages over the ...
5
votes
1answer
47 views
Two languages such that $L_1 \cup L_2 \leq_m\, L_1 \cap L_2$ and two (other?) such that $L_1 \cap L_2 ≤_m\, L_1 \cup L_2$?
Are there languages $L_1$, $L_2$ such that such that
$$L_1 \cup L_2\leq_m\, L_1\cap L_2,$$
and two other languages such that
$$L_1 \cap L_2 \leq_m\, L_1 \cup L_2?$$
And if so, what are they? How ...
1
vote
0answers
25 views
How to visualize non-deterministic pushdown automata?
My friend and I are working on this project for our Formal Languages and Automata class that consists in building a pushdown automaton. A part of the project that is bothering me is how to visualize ...
