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