Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques

learn more… | top users | synonyms

1
vote
1answer
13 views

is language accepted by finte state automaton

Hi I need to prove these languages are accepted or not by the following finite state automata. for 1 does this mean that we need an even number of a's or that a is literally 2,4,6,8....etc also ...
0
votes
2answers
35 views

Is this language Regular or is it not?

$L=\{0,011,011000,0110001111,\dots \}$ Generates string of the form: $0^1 \\ 0^1 1^2 \\ 0^1 1^2 0^3 \\ 0^1 1^2 0^3 1^4 \\ 0^1 1^2 0^3 1^4 0^5\\ \dots$
2
votes
1answer
35 views

Why is this language not regular?

I am studying Automata using the Coursera course created by Jeff Ullman. On slide 36 of this presentation: http://spark-public.s3.amazonaws.com/automata/slides/3_fa2.pdf it says that the language is ...
1
vote
1answer
22 views

How to simulate a 3-stack automaton with a 2-stack automaton?

Since a 2-stack automaton is Turing-equivalent, it is possible to simulate a 3-stack automaton with just a 2-stack automaton. But how so? How it is normally done?
4
votes
3answers
130 views

Number of states in a finite automaton

How many states are required by a deterministic finite automaton to store $m$ words each of length $n$? I came across $2^{mn}$ as the solution but there was no explanation.
2
votes
1answer
37 views

Is the Champernowne constant an automatic number?

The Champernowne constant in base $b \geq 2$ is obtained by concatenating the $b$-ary expansion of every integer. For example, in base $10$ this is $$ 0.123456789101112131415\dotsc $$ Question: Is the ...
1
vote
1answer
20 views

Why Petri Net tokens are not added?

Reading this article it says: A firing of an enabled transition removes one token from each input place and adds one token to each output place. Now if I have the following net, with all ...
0
votes
0answers
9 views

inverse proof of closed under union

I am being posed the following question: given are languages $L_1, L_2, L_3 $ and $ L_4$. $L_1$ is a decidable language and $L_2$ and $L_4$ are both recognizable languages. Considering $L_1 = L_2 ...
1
vote
1answer
42 views

How n (1+b) is not prime?

Here is the complete proof taken from this link How do I convince myself that n(1+b) is not prime when b>=1? Here is what I did: if n is 3 and b is 3. Then ...
0
votes
2answers
26 views

Why is the below language regular?

If I have a language $$L=\left\{wxwy : w,x,y \in \{a,b\}^+ \right\}$$ I am not getting how come we are able to write regular expression for this of the form $$a(a+b)^+ a(a+b) ^+ + b(a+b)^+ b(a+b) ...
2
votes
1answer
29 views

pumping lemma for CFL vs pumping lemma for regular languages

Is the pumping lemma for context free languages a generalization of the pumping lemma for regular languages (for instance if we set $u=\epsilon, v=\epsilon$ we can then relate $wx$ in the pumping ...
0
votes
1answer
31 views

Quick question on DFA

I'm asked to list all DFA over the alphabet sigma = {0} such that the set of states is {s0, s1}, for which the initial state is s0 and the set of accept states is either {s0} or {s1}. And also asked ...
0
votes
0answers
19 views

Best approach to determine the equivalence classes of a formal language

I created a minimum automaton for a formal language using the Myhill-Nerode theorem. The language for which I created the automaton is defined by $L=\{w \in \{a,b\}^*:w=av \text{ for a word } v ...
1
vote
0answers
28 views

Construct PDA that accepts the language $ L = \{ w \in \{ a,b,c\}^*; |w|_c=|w|_a + |w|_b \} $

Problem Construct PDA that accepts the language $ L = \{ w \in \{ a,b,c\}^*; |w|_c=|w|_a + |w|_b \} $ My first idea was this: There can be an "a","b" or a "c" at the beginning of a word Then we ...
0
votes
2answers
23 views

How to draw a DFA for complement of a regular language using a regular expression?

How can I draw an FA for the complement of the language $L(r)$? $L(r) = a^* (aba^*)^* b^* a^*$ I can draw an FA for $L(r)$ and convert to DFA and then take the complement, however it seems very long ...
1
vote
2answers
41 views

Proving that $L := \{a^n\mid\exists k \geq 0\ n = k^3\}$ is not a regular language

I'm having trouble using the pumping lemma to prove this language $L := \{a^n\mid\exists k \geq 0\ n = k^3\}$ is not regular. Assume $L$ is regular. Thus there is a DFA $M$ for it. Choose $m$ as the ...
2
votes
1answer
18 views

Concatenation of Finite Languages and Regular Languages

I know that the following statements regarding Concatenation are false. However, I'm having difficulty explaining why they are false with simple counter-examples. I'm able to find simple ...
1
vote
1answer
59 views

Why are Recursively enumerable languages closed under intersection?

when Recursively enumerable sets are not closed under complement ,then how come they are closed under intersection because the definition of intersection comes as L1 intersection L2= complement(L1' ...
-1
votes
2answers
25 views

Is the intersection of a finite language and an infinite language always a regular language?

Is the intersection of a finite language $L_1$ and an infinite language $L_2$ always a regular language? I've tried a few examples and the result always seems regular. $\{\} \cap a^nb^n = \{\}$ ...
0
votes
1answer
33 views

Context-free language or not

It is language: $L = \left\lbrace a^ib^jc^kd^l \mid i+k < j+l+3 \right\rbrace$ Is it context-free or not? I have two versions: 1)Pumping lemma(refute): get a word $uvxyz = aabcd$ if $i=2$ we get ...
1
vote
1answer
26 views

Minimum Size of DFA

I'm confused about the following DFA problem: Let L denote the set of all strings in $\{a, b\}^∗$ that contain abb or aab as a substring. Show that any DFA that decides L must have at least five ...
0
votes
1answer
18 views

Proving from Myhill-Nerode that the minimum DFA is the smallest automaton recognizing $L$

From this paper, In the proof of (Myhill-Nerode theorem) it's stated that if $L$ is a regular language and the index of $\sim_L$ is $i_L \in \mathbb{N}$ then it's both necessary and sufficient for ...
0
votes
1answer
49 views

Context free grammar $\{a^n b^m c^k\; : \;k>m \; \; k>n\}$

Is this a CFL? $$\{a^n b^m c^k\; : \;k>m \; \; k>n\}$$ When on seeing $a$'s and $b$'s I push them onto stack and as I see $ c$ as input if $ TOS$ is $b$ ,I pop them ,again if $TOS$ is a,I pop ...
1
vote
1answer
33 views

Construct a deterministic finite state automaton

Construct a deterministic finite-state automaton that recognizes the set of all bit strings that end with 10. This is what I drew. Not sure if its correct. State 2 is the final state. Am I missing ...
0
votes
1answer
20 views

Find the language recognized by the given deterministic finite state automaton

I got 01* U 1(01)01 as my answer. I'm not sure if its right.
0
votes
0answers
13 views

4th case in Ogden's Lemma

I'm trying to understand Ogden's Lemma and I know there are four cases, but in the next example I can only find 3: A = {$0^n1^m0^k$ | k = max{n,m}} is not context free: Assuming: z = $0^k1^k0^k ∈ A$ ...
0
votes
1answer
23 views

How to find the right quotient of a language given two languages?

If $L_1= \{a^n b^m \mid n \geqslant 1, m \geqslant 1 \} \cup \{ba\}$ and $L_2= \{b^m \mid m \geqslant 0 \}$. I am not getting how the DFA for $L_1/L_2$ is constructed in the second figure ...
2
votes
1answer
43 views

Designing a Turing Machine - low level transitions

I couldn't figure out how to proceed with this question. Preparing for the finals, can someone explain how to do this step by step? Design a TM, write low level transitions for $\{a^i b^j :i ≤ j ≤ ...
1
vote
1answer
29 views

Let $LOOP_{TM}$ be descriptor language of all touring machines that won't halt for any input. Show reduction of $HALT_{TM}$ to $LOOP_{TM}$

Question from Homework that I'm having difficult to answer on: Let $LOOP_{TM} = \{\langle M\rangle \mid \text{M is a TM that does not halt on any input w}\}$ Let $LOOP_{TM}$ be descriptor ...
0
votes
2answers
31 views

Converting an NFA to DFA

I am atttempting to convert an NFA into an equivalent DFA. I did it, but i am not sure if it is correct. If anyone can please take a look at let me know if it is correct or if there is something wrong ...
2
votes
1answer
18 views

Finding regular expressions for which a given Turing machine halts and accepts, halts and rejects, and diverges.

Consider the Turing machine M = (Q,Σ,Γ,δ,q,F) F = {t} Q = {q,r,s,t,v,x} Σ = {a,b,c} Γ = {B,a,b,c} δ = [q,a,q,a,R] [q,b,q,b,R] [q,c,v,b,R] [q,B,r,B,L] [r,a,s,B,L] [r,b,s,B,L] [r,c,s,B,L] ...
0
votes
1answer
29 views

Graph and language/automaton equivalence

I'm looking for a reference rather than an answer. I think I'm just not Googling the right combination of terms. I imagine that there is a class of graphs which is equivalent to some class of ...
0
votes
2answers
15 views

Languages and their Regular Expressions - Automata

I am working on some Automata practice problems. I am working a 2 part question. Here it is: Let $\Sigma = \{a,b\}$ be an alphabet. Let $L = \left\{w \in \Sigma^* \mid n_a(w) \le 4\right\}$ ...
1
vote
1answer
25 views

Pumping Lemma proof and the union/intersection of regular and non-regular languages

I am still learning the pumping lemma. I have a problem for which I used it. I used it on the first part (a) but I am unsure if it is correct. Parts b-d, I am not sure how to do it. I created a dfa ...
0
votes
1answer
20 views

Using the Pumping Lemma To Prove A Language Is Not Regular

I am taking a Automata class and we just went over the Pumping Lemma. Initially, it did not make sense. I am still not fully comfortable but I have started trying to use it to prove that a language is ...
2
votes
1answer
19 views

Prove that regular languages are closed under operation

Operation $random$ is defined on two words with equal length in the following way: $\forall w_1,w_2 \in \Sigma^* s.t. |w_1|=|w_2|=n, w_1=a_1a_2...a_n, w_2=b_1b_2...b_n:$ $Random(w_1,w_2) = ...
0
votes
1answer
26 views

Explain the semantics of concurrent languages with real analysis examples

In computer science, concurrency is a property of systems in which several computations are executing simultaneously, and potentially interacting with each other. I need to explain the concurrency ...
0
votes
0answers
84 views

Determinitic finite automaton (DFA) that accepts natural numbers divisible by 6

I'm new to Formal Systems and Automata and I'm working on some exercises to get familiar with the concepts. I want to create a DFA that accepts natural numbers divisible by 6. I know that a number ...
1
vote
1answer
45 views

NFA (nondeterministic finite automaton) made out of the Bible?

Let B be the language over alphabet {a, ... z} consisting of those words occuring in the Bible. Thus, B = {in,the,beginning,god,created,...}. Describe an NFA whose language is B. Describe what ...
1
vote
1answer
45 views

Write grammar for given language

I'm trying to write a grammar for the language below: $$(a+b)^*−\{𝑤𝑤𝑤 ∶ 𝑤\in\{a,b\}^*\}$$ could anyone help me?
0
votes
0answers
36 views

Is the sequence $(v_p(n))$ of $p$-adic valuations of positive integers the fixed point of a morphism, for every prime $p$?

Fix a prime number $p$ and consider the sequence $\mathbf{v}_p = (v_p(n))_{n \geq 1}$, where $v_p$ is the usual $p$-adic valuation, i.e. $v_p(n) = a$ iff $p^a \parallel n$. While browsing the OEIS I ...
1
vote
1answer
26 views

what do we mean by saying that a particular computing machine is more powerful than another computing machine?

I am having confusion in understanding the concept of the word "powerful" in automata theory. Even the confusion arises that if I have a DFA with single final state ,so then is it more or less ...
1
vote
1answer
30 views

Is $L = \{0^{i}1^{i}0^{j}1^{i} | i, j > 0\}$ a context free language?

Is the following argument correct? $L = (A \circ B) \cap C$ where, $A = \{0^{i}1^{i}$ $|$ $i > 0\}$ $B = \{0^{j}1^{i}$ $|$ $i, j > 0\}$ $C = \{0^{i}1^{j}0^{k}1^{i}$ $|$ $i, j, k > 0\}$ We ...
2
votes
3answers
273 views

What is the easiest way to determine the accepted language of a deterministic finite automaton (DFA)?

I'm new to automata theory and I'm currently working on some exercises on determining the accepted language of DFAs. I was wondering whether there exists some clever strategy to determine the accepted ...
1
vote
1answer
24 views

Transition function of the generalized nondeterministic finite automata

Why does the transition function of a GNFA map from two states to a regular expression $$ \delta: (Q \setminus \{q_{start}\}) \times (Q \setminus \{q_{accept}\}) \to R $$ instead of mapping from the ...
2
votes
2answers
43 views

A Regular Expression for all strings that…

I got a problem I have to solve, the problem says that given an alphabet $\Sigma = \{a, b, c\}$ I have to build a regular expression that describes the string with: An even number of a's. A 4k + 1 ...
0
votes
0answers
14 views

Where does $b(10)$ goes under this automaton

This is finite state automaton for Grigorchuk group. I have never studied automaton formally, so I wanna check is it fine the way I am doing it. Here $\epsilon$ change the first entry on string ...
2
votes
0answers
59 views

How to show $L = \{a^n b^m c^p: n\neq m\} \cup \{a^n b^m c^p: m\neq p\}$ is ambiguous?

I'm recently familiar with this site and prefer to ask a very hard problem :) How can we prove that the following language is inherently ambiguous? $$L = \{a^n b^m c^p: n\neq m\} \cup \{a^n b^m ...
1
vote
1answer
48 views

Is it possible to write an Unambiguous Grammar for Two Hard Language ?!?

I came across a very hard interview exam. It was asked wrote an unambiguous grammar for two following language, Who can hint it to solve it? 1) $L = \{a^n b^{2n} c: n\geq 0\} \cup \{a^{2n} b^n d: ...
1
vote
0answers
48 views

Where is my mistake in this DFA minimization?

I'm currently having trouble minimizing my DFA. I have the following graph: (ignore the numbers after ":") Using the table minimization method I reached: (x is distinguishable, O is ...