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

learn more… | top users | synonyms

3
votes
1answer
28 views

Is C* regular if C is a language with strings of prime length?

Let $C = \{a^p \ | \ p \ \text{is prime}\}$ be a language. I was able to show that $C$ is not regular using the pumping lemma. However, I am having some trouble showing that $C^*$ is regular. ...
-1
votes
2answers
45 views

Can $L$ be regular language if it is a union of infinitely many regular languages $L_1,L_2,L_3,…$ over the same alphabet?

Can $L$ be regular language if it is a union of infinitely many regular languages $L_1,L_2,L_3,...$ over the same alphabet ? (a) can $L$ be regular ? (b) Is $L$ always regular ? I want to make sure ...
1
vote
3answers
37 views

If $L_1$ and $L_2$ are regular then $L_1 \cup\;L_2\; = L$ is regular. Is the converse true?

The following is an answer I found to the question. For instance, $\sum^*$ is a regular language; but it can be decomposed into two languages $L_1= \{0^i1^i,\;i\ge0\}$ and $L_2 = ...
0
votes
3answers
62 views

What is the difference between regular expression $(x + y)^*$ and $(x^*y^*)$? [closed]

What is the difference between regular expression $(x + y)^*$ and $(x^*y^*)$ ?
1
vote
2answers
60 views

Why is $L=\{xww^r \mid \text{ $x$, $w$ belongs to }(a+b)^+) \}$ not regular?

If I have a language $L$ such that $L= \{xww^r \mid \text{ $x$ and $w$ belong to }(a+b)^+) \}$. Then can't we write regular expression for this to be $(a+b)^+(ab+ba)$? What's wrong in this regular ...
0
votes
1answer
32 views

Constructing automata for regular languages [duplicate]

I have two languages: $\{a^n b^m \mid n, m > 0, n - m = 0 \pmod 3\}$ $\{a^n b^m \mid n, m > 0, n + m = 0 \pmod 3\}$ and I'm having trouble drawing automata for them. For the first language, ...
0
votes
1answer
55 views

Drawing automata for languages

I'm trying to draw two automata for these two languages: For the first one, I know that the minimum is n = 1, m = 1, but I'm having troubles drawing a NFA for it. The second one the minimum is n = ...
0
votes
0answers
18 views

Converting regular expressions to NFAs

I'm having trouble converting these regular expressions to NFAs For 1, does the plus sign mean I should draw each term individually and then make an epsilon state between them? Would this be ...
0
votes
1answer
23 views

regular expressions, notation w|w and w|?

I'm trying to give regular expressions for the following languages {a, b} What does w| and w|w mean? For the first question, I have (b(a+b))*, but I'm lost on the second.
0
votes
2answers
60 views

regular expressions $(a+b)^*$

If I have a regular expression $(a+b)^*$, does that mean I can't have the string $abba$ because the expression ends with a $b$? Or does this expression accept every string in the alphabet $\{a, b\}$?
0
votes
1answer
46 views

language of bitstrings with no more than 3 consecutive zeros generating function

I am trying to find the generating function of a sequence in the language of bitstrings, $X$, where each bitstring contains no more than 3 consecutive zeros. I have come up with the recurrence ...
2
votes
1answer
60 views

What are annihilators?

I was recently listening to Automata lecture, there it was told told that an empty set is an Annihilator for concatenation just like $0$ is for multiplication. What do we mean by this statement?
1
vote
1answer
62 views

recurrence relation of a language

I am looking at the following: Consider a language $X$ which consists of all bitstrings with no more than 2 consecutive zeros (represented by the above automaton). Next consider a sequence $s_n$ ...
-1
votes
1answer
19 views

If Language $L_1$ is accepted by a Pushdown Automata and Language$ L_2$ by a Turing Machine, Is $L_1 \cup L_2$ accepted by a Pushdown Automata?

Let $L_1$ be a language recognized by a Pushdown automaton and let $L_2$ be another language recognized by a Turing machine. Is $L_1 \cup L_2$ recognized by a Pushdown automaton? Prove your answer.
0
votes
1answer
151 views

The complement of a language of a machine L(M)

I'm asked these two questions: a) Is it true that for any Non-deterministic Finite Automata $M=(Q,\Sigma, \delta, q_0, F)$, the complement of $L(M)$ is equal to the set $\{w \in \Sigma^* : ...
1
vote
2answers
54 views

Regular Expression to a Deterministic Finite Automata with Kleene Closure

I'm asked to make a DFA for the following: $\Sigma = \{a, b \} $ and $\{ $ w | w does not contain the string ab $ \}$. My first approach was to convert this into a regular expression by taking the ...
2
votes
1answer
38 views

Pumping Lemma Proof for non-regular languages

Okay, so this is a confusing and abstract topic. I'm having some trouble proving a language is not regular using the Pumping Lemma. Suppose I have: $L = \{ a^ncb^n | n >0\}$ I know for a fact ...
2
votes
2answers
236 views

What are closure properties of regular languages?

In class we've been talking about DFA's and NFA's and being closed under ____. The homework problems say to "use closure properties of regular languages to show that a regular languages are closed ...
0
votes
2answers
76 views

If every NFA is a DFA, the fact that I can make an NFA to a single accepting state proves that I can also do it for a DFA? is that enough?

The question is: Prove that every NFA can be converted into one with a single accept state. Is the same true for DFAs ? Prove your answer. I already did the first part of proving that NFA's can be ...
0
votes
1answer
31 views

Transforming a CFG into a PDA with single state

Can I always transform a context-free grammar into a pushdown automaton with a single state? How can I do that? I cannot find any explanation how to do that.
1
vote
3answers
59 views

Does the Kleene Closure of an alphabet contain an infinite string?

Suppose we have an alphabet $\Sigma$, does $\Sigma^*$ contain an infinite string? My reasoning is, since $\Sigma^*$ contains an infinite number of strings, one of those strings must have an infinite ...
1
vote
1answer
45 views

Alphabets of Turing Machine

I'm not completely sure about equivalence of two definitions of Turing machine. The first one states that Turing machine has a finite alphabet $\Sigma$, set of states and some rules. Turing machine ...
0
votes
1answer
19 views

finite-state machine for a system

Every cycle we get a bit $x_t$. We output $1$ iff $$(x_1\ldots x_t) \bmod 5 = 2 \lor (x_1\ldots x_t) \bmod 5 = 4$$ I need to design an FSM (preferably Mealy machine but that doesn't really matter. ...
0
votes
3answers
74 views

Is the language $L$ generated by 'Fibonacci Strings' (as given in the desciption) regular? If not, disprove by Pumping Lemma

The Fibonacci strings are defined as follows: $S_1=a$, $S_2=b$ and $S_k=S_{k-1}S_{k-2}$ for $k>2$ . For example $S_3=ba$ , $S_4=bab$ etc. Let $L$ be the language generated by the Fibonacci strings. ...
-2
votes
2answers
60 views

What are good techniques for creating a DFA state diagram given a set of accepted/rejected strings?

I am in a Discrete Structures class and my teacher is pretty big on proving his intellect to the class and getting an average of about 60% for his test questions. Right now we are working with ...
1
vote
0answers
39 views

NFA that accepts binary strings starting with 1 and with at least 01, or at least 010, or both. [closed]

Im not sure if I am understanding this question correctly. Its a problem without a solution in my text. Starting with 1, and at least 01 or at least 010 or both these substrings..... So a regular ...
0
votes
1answer
160 views

Is dead state only linked with the final state in any automata?

I am very much new to this subject and as far as I have tried the small research I found this most meaningful at this link Dead State - A rejecting state that is essentially a dead end. Once the ...
0
votes
1answer
64 views

Boolean formulas over omega automata

I've been reading on omega automata(automata on infinite words) and stumbled upon a definition involving logic which caught me off guard. For example, on Buchi automata the definition I originally ...
-1
votes
2answers
57 views

Prove that $R_1 \times R_2$ is a regular language for $R_1, R_2$ regular [closed]

Let A and B be two sets. The cross products of A and B are defined as : AxB={(a,b): a belongs to A and b belongs to B }. Assume R1 and R2 are regular languages over an input alphabet Σ={a,b}. Prove ...
0
votes
0answers
30 views

Inequality for the set of factors of length $n$ of some regular language

If $W \subseteq X^*$ is some language denote by $$T(W) := \{ u \in X^* : \mbox{there exists }x, y \mbox{ such that } xuy \in W \}$$ the set of factors (infixes) of $W$. If $W$ is regular, then ...
2
votes
2answers
41 views

Set of all factors of regular language regular?

If $L$ is a regular language (i.e. acceptable by a finite automata), is the the set of its factors (infixes) also regular?
0
votes
2answers
49 views

Can finite automata keep track of history or relevant history?

I am unable to understand that if I have a Finite automaton which say accepts all the strings that end with ab, now if input given is "aab" now it reads 'a', then it reads second 'a',this implies ...
2
votes
2answers
72 views

Finite automata as dynamical systems

In abstract (deterministic finite) automata theory the set of states of an automaton is an arbitrary set Q, and the transistion function is a specific set δ ⊆ Q × Σ × Q (with alphabet Σ, i.e. another ...
1
vote
0answers
71 views

Does a mathematical construct exists which explains all theories?

If I am not wrong quantum mechanics is about measurements of different physical properties and probabilities of getting different outcomes. We have a mathematical construct to explain it, that is how ...
6
votes
2answers
107 views

Describe and count the set of sequences containing $20$ or $02$

Let $X = \{ 0,1,2 \}$ be a ternary alphabet and denote by $X^*$ the set of finite sequences (i.e. strings) with three symbols. For $w \in X^*$ with $n$ the length of $w$ and $w = w_1 w_2 \cdots w_n$ ...
2
votes
1answer
69 views

DFA/NDFA problems confirmation

Im studying for a test on my own and have been working through some previous test questions. Can anyone help me confirm that the answers I've gotten for the problems below are correct or not. If there ...
1
vote
2answers
42 views

How to design a finite state automaton that recognises the languages like $1^n 0^n$

The question goes like this: Design a finite state automaton that accepts binary strings with at least two $0$s and at most two $1$s. I can easily design an NFA which accepts at least two $0$s OR at ...
2
votes
2answers
55 views

Is the language $\{yxzx^Ry^R \mid x,y,z \text{ belongs to } \{0,1\}^+ \} $ regular?

This is a question from Iran's national grad school entrance exam. In the answers key, the answer was that the following language is regular but I doubt it is true, I proved using pumping lemma that ...
1
vote
2answers
74 views

Number of finite-state machines with $n$ states, output alphabet size $a$, and binary input

How many FSMs are there where the machine has $n$ states, reads a binary symbol at each time-step, and may or may not output a symbol from an alphabet of size $a$ after each transition?
1
vote
1answer
25 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 ...
2
votes
1answer
40 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
41 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
324 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
44 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
24 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
21 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
44 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
35 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
96 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
152 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 ...