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

learn more… | top users | synonyms

2
votes
3answers
101 views

Create a formal regular expressions that accepts all strings of 1 and 0 that do not contain 101

I'm working through a textbook on automata theory and I'm stuck on this regular expression problem. Create a regular expression for the following language: The set of all strings that do not contain ...
0
votes
1answer
41 views

Prove if a language is infinite

Given M = (Q,Σ,δ,q0,F) a DFA with n states. Prove: The languge T(M) is infinite iff contains a string with lenght t, where n ≤ t < 2n. Ok, it's intuitive for me, I can understand to get a string ...
0
votes
1answer
24 views

Find languages L1 and L2, neither of which contains the other, such that (L1* ∪ L2*) = (L1 ∪ L2)*. [closed]

I'm trying solve this question in several ways, but only textbook has not helped me alot.
0
votes
1answer
42 views

Is $L = \left \{ a^m b^mca^nb^m \mid m,n \geq 0 \right \}$ context free language?

I have doubt , regarding this question Is this language is context free ? $L= \left \{ a^m b^mca^nb^m \mid m,n \geq 0 \right \}$ IMO : push all $a$'s , match with $a$ and pop $b$'s ,(now stack ...
1
vote
0answers
34 views

Probability Assessment of Interactive Markov Chain (IMC)

Firstly, consider a Markov chain in your mind. Probability of each state of the Markov chain can be obtained by following Chapman–Kolmogorov equation. $$ P(n\Delta t) = M^{n}P(0) $$ where P is the ...
0
votes
0answers
150 views

Construct DFA from context-free grammar

What is simplest and shortest way to build minimal DFA from context-free grammar (equivalent to regular grammar)? For example, the grammar: A ::= aB B ::= {b} ...
0
votes
1answer
28 views

For DFAs, NFAs how can you show $L(D) = \overline {L(D')}$ or $L(N) = \overline {L(N')}$?

Sorry if the title doesn't completely explain the question but I couldn't find a way to fit it all in there. I am having some trouble with the following question: Image In particular, I do not know ...
0
votes
2answers
49 views

number of NFAs given $a$ states

If $a$ and $b$ are positive integers. How many NFAs can there be with $a$ states and the input alphabet, $\Sigma = \{0, 1, . . . , b − 1\}$
0
votes
0answers
44 views

Union of two Non deterministic Finite automata

How to perform union of two NFAs. This question is from Peter Linz's book. Find an NFA with four states for $L=\{ a^n \ | \ n \geq 0 \} \cup \{b^n a \ | \ n \geq 1\}$. Now Considering the first part ...
3
votes
1answer
36 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
51 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
39 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
65 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
69 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
33 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
57 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
77 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
50 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
71 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
174 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
63 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
41 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
333 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
133 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
42 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
72 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
54 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
22 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
105 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
64 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
42 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
296 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
65 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
61 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
31 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 ...
1
vote
2answers
51 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
80 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
72 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
114 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$ ...
1
vote
1answer
78 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
43 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
57 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
88 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
26 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
43 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 ...