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

learn more… | top users | synonyms

2
votes
1answer
167 views

Can you draw the e-NFA from the following definition?

I am trying to understand the solution, because I think I got it completely wrong. I wrote we could take the initial DFA and replace the normal transitions with epsilon transition except for all ...
2
votes
2answers
49 views

Regular Expressions Help [duplicate]

I need a little help with Regular Expressions. The allowed operations are obviously + (union) , * (Kleene star) and concatenation. I have to write Regex for the following 2 examples. I have tried a ...
2
votes
2answers
74 views

Prove the following by using mathematical induction

If we define the alphabet such that $$ \Sigma = {\{a,b}\} $$ and let $w$ be a string over it. I'd like to prove $$ ( \operatorname{comp}(w))^R = \operatorname{comp}(w^R) $$ where $$ w^R$$ and ...
2
votes
1answer
2k views

Proof of Equivalence of NFA and DFA, quick question about the setup

I am looking at the proof of equivalence of non determinstic finite automata(NFA) and deterministc finite automata(DFA). I am have a small quesion about the construction: Let ...
2
votes
1answer
92 views

Prove that RE is closed under reduction

Prove that the class RE is closed under reduction. Definitions: A language $ A \subseteq \Sigma^*$ is called reducible to $ B \subseteq \Gamma^*$ ( denoted by $A \leq B$) if there is a computable ...
2
votes
1answer
83 views

Language concatenation

We learned in class that the regular languages are closed under concatenation (e.g $L_1L_2 =\{ w_1w_2 : w_1 \in L_1,w_2 \in L_2\}$ is a regular language if $L_1$ and $L_2$ are also regular ...
2
votes
2answers
49 views

Turing decidable/undecidable

let $X = \{\langle M \rangle\ |\ M\text{ is a finite state machine and }L(M) = \emptyset\}$ where $\langle M \rangle$ is an encoding of the machine $M$. can you prove whether $X$ is Turing ...
2
votes
1answer
86 views

Formal proving of languages accepted by a finite automata.

Suppose $L_1 \cup L_2,L_1 \subseteq E^* $ are languages accepted by finite automata and $L_1\cap L_2 =\emptyset $. We need to prove that $L_2 $ is also accepted by a finite automaton. So I've started ...
2
votes
1answer
488 views

Verification: DFA/NFA that accepts all strings over $\{0,1\}$ with exactly one block of $00$

I am trying to design a DFA or NFA that accepts all strings over $\Sigma = \{0,1\}$ in which the block $00$ appears only once. Here is what I've tried. Can you verify that this accepts all string ...
2
votes
1answer
78 views

Is there an (explicit?) bijection from the set of all automatons to the set of all regular expressions that conserves the recongnised language

Let $\Sigma$ be an alphabet, $R$ be the set of regular expressions on $\Sigma$ (that is, trees with leave's values in $\left\{\varepsilon\right\}\cup \Sigma$ and three types of interior nodes, one ...
2
votes
1answer
145 views

DFA worst case states

Suppose an NFA which accepts language of the form L(N) = {w| w has 1 in n$^t$$^h$ from last symbol.} Then the corresponding DFA would have 2$^n$ states(worst case of subset construction). If we are to ...
2
votes
1answer
952 views

How to construct a grammar $G$ such that $L(G) = \{ a^nb^m|n \neq 2m,m,n \ge 0\} $?

Construct a grammar $G$ such that $$L(G) = \{ a^nb^m|n \neq 2m,m,n \ge 0\}$$ My attempt: I first constructed a grammar for the langugage $L(G_1) = \{ a^nb^m|n = 2m,m,n \ge = 0\}$, $G_1 = (\{ S\}, ...
2
votes
1answer
68 views

Is regularity is preserved under reversal?

When talking about languages and regular languages. Can I say that reversal preserved regularity since if the language L is regular, we can generate it by right linear grammar. Therefore, the ...
2
votes
1answer
2k views

Show two finite state machines are equivalent

Suppose $M_1 = \langle Q_1,S,R,f_1,g_1\rangle$ and $M_2 = \langle Q_2,S,R,f_2,g_2\rangle$ are two strongly connected machines. I need to show that $M_1 \equiv M_2$ iff there exist a state $p \in Q_1$ ...
2
votes
1answer
157 views

Is the set of codes of Deterministic Finite-State Automata a regular language?

Let $\Sigma$ be a given alphabet. Is there a way to code up Deterministic Finite state Automata (DFA) over $\Sigma$ as strings of $\Sigma$ in such a way that the corresponding subset of $\Sigma^*$ is ...
2
votes
1answer
247 views

Constructing finite state automata corresponding to regular expressions. Are my solutions correct?

I have drawn my answers in paint, are they correct? (4c) For the alphabet {0, 1} construct finite state automata corresponding to each of the following regular expressions: (i) 0 My Answer 4ci (ii) ...
2
votes
1answer
42 views

Is the complement of a given language context-free?

I have a problem with finding out if the complement of language L is context free. $L = \{ ww : w \in \{a,b\}^{*} \wedge \text{ }w \text{ number of }a\text{'s in }w \equiv \text{number of }b\text{'s ...
2
votes
1answer
47 views

Understanding Turing Machines: Recognizable and Decidable langauges

I've searched tons of resources and while conceptually I understand the turing machine itself and what it does- I'm a bit stuck on Turing Recognizable and Turing Decidable languages and I'm not sure ...
2
votes
0answers
19 views

Writing a regular expertion for the language $L=\{0^n1^m|n\equiv m(\mod 2)\}$

I need to write a regular expertion for the language of all the binary words that contains continuum of even number of zeros and after that even number of ones or odd number of zeros and after that ...
2
votes
0answers
51 views

Regular expression for string's of a's and b's beginning with b and not having two consecutive a's

Question: Write a regular expression for the following language: "All strings of a's and b's in ∑* beginning with b and not having two consecutive a's. A textbook says the answer is (b+ba)*. ...
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
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 ...
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 ...
2
votes
1answer
49 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 ≤ ...
2
votes
1answer
28 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] ...
2
votes
0answers
70 views

Trouble with induction on the length of a word

In the accepted solution of the question If L is regular, prove that $\sqrt{L}=\{w:ww\in L\}$ is regular the answerer made the claim that "What's left is to show that $δ ′ (q_{0}' ,w)=h$ , which can ...
2
votes
0answers
272 views

nth-root of continued fraction with Raney transducers

There are some algorithms for doing basic arithmetic by using regular continued fraction expansions. These algorithms are mainly due to Gosper (1972) and Raney (1973). These two approaches use ...
2
votes
1answer
94 views

Show that the function floor-log is primitive recursive

I have been stuck on this problem for a while and I was hoping someone could help me with it. This is for my computer science automata and formal languages class. Given an integer $b$ greater than or ...
2
votes
0answers
42 views

show that language is regular

Let $B_n = \{a^k\ |\text{ where } k\text{ is a multiple of } n\}$. Show that for each $n\ge 1$ the $B_n$ language is regular. My proposition of solution: What about it ?
2
votes
1answer
52 views

Intersection of context-free language and its reversal

I know that intersection of two context-free languages is not always context-free and the following problem: Given two context-free languages A and B, is $A \bigcap B \neq \emptyset$ ? is ...
2
votes
0answers
41 views

Size of automata or regular expressions avoiding cross patterns

Let $\Sigma$ be an alphabet of finite size $k$, and $n$ some integer. I am interested in the language of words of size $n$ that do not contain $abab$ as a subword, for any pair $(a,b) \in \Sigma$ (I ...
2
votes
1answer
102 views

Is it possible to make a PDA for $\{ ww : w \in \{ 0,1 \}^* \}$?

Consider the language $L = \{ ww : w \in \{ 1,0 \}^* \}$. I know it's easy to make a PDA for $\{ w w^\text{R} : w \in \{ 0,1 \}^* \}$ where $w^{\text{R}}$ is the reverse of $w$, but I can't think of ...
2
votes
1answer
186 views

Pumping Lemma for regular languages proof template

http://www.cs.uiuc.edu/class/fa06/cs273/Lectures/pumping-lemma/pumping-lemma.html So, I went to that site and it says: $w = xyz$ $|xy| \leq p$ $|y| \geq 1$ for all $i$, $xy^iz$ is in ...
2
votes
1answer
87 views

Context free grammar for language

I'm learning how to generate context-free grammar for a language. $L=\{{a}^i {b}^j {c}^k\, |\,i=j\lor j=k$ Here is how I tried ...
2
votes
0answers
72 views

halting problem

Prove that it is undecidable for the halting problem of a deterministic Turing machine which accepts nonrecursive language or in-other-words: let's say we have a deterministic Turing machine which ...
2
votes
0answers
125 views

Blanks in the Tape of a Turing Machine

I used to have a lot of trouble with Turing Machines, primarily because I thought that in-between input symbols on the tape, one could have an arbitrary number of blanks, so every input would need to ...
2
votes
1answer
114 views

Build regular expression from language

I have the following language: L = {w $\in$ {a,b}* | aa is not part of w}. I have to construct a regular grammar from this language and I thought about first finding the regular expression from the ...
2
votes
0answers
71 views

Turing Machines

Suppose that $\Sigma$ is a finite set and that $L_1$, $L_2$ and $L_3$ are Turing acceptable subsets of $\Sigma^*$ that satisfy the following properties: $L_1 \cup L_2 \cup L_3 = \Sigma^*$; $L_1 \cap ...
2
votes
1answer
388 views

Converting CFG to CNF

I have the following problem of converting CFG to CNF: $$ \begin{aligned} S \Rightarrow\,& bA \mid aB\\ A \Rightarrow\,& bAA \mid as \mid a\\ B \Rightarrow\,& BB\mid bs\mid b ...
2
votes
1answer
32 views

Properties of “fail-safe” languages

I'm wondering if anyone has any experience with the concept of a "fail-safe" language. And, if so, where could I find more information on the subject. To explain what a "fail-safe" language is: Let ...
2
votes
0answers
32 views

Is there a 2D 3-colorstate mobile automaton that grows like $ln^{0,5}(t)$?

Define an integer function $f(t)$ for an integer $t>25$ such that $|f(f(t)) - ln(t)| < \sqrt {ln(t)}+2$. Define $L(X(t))$ as the number of nonwhite states at iteration $t$ of mobile automaton ...
2
votes
0answers
65 views

Expressiveness of finite memory programs

Assume we have a simple programming language with while, if, := (assignment), ...
2
votes
0answers
53 views

Quality of Reduction of finite automata

I am looking for an example, which corresponds to what I've learned in my Applied Automata Theory Class: Given a NFA $\mathcal{A}$, a $\approx _\mathcal{A}$ quotient automaton can be bigger then a ...
2
votes
2answers
197 views

An NFA with $\Sigma = \{1\}$ with $x^2$ accepting runs on strings $1^x$ for all $x \geq 0$ - how to construct?

One of my homework assignments requires us to construct an NFA over the alphabet $\{1\}$ which has exactly $x^2 + 3$ accepting runs over the input string 1^x for all $x \in \mathbb{N}$. Now, the +3 ...
2
votes
0answers
140 views

Mathematical formulation of 'Indra's net' [closed]

Quoting Wikipedia: "Imagine a multidimensional spider's web in the early morning covered with dew drops. And every dew drop contains the reflection of all the other dew drops. And, in each ...
1
vote
2answers
347 views

Converting from NFA to a regular expression.

This is a NFA, I have been working to covert it to a regular expression. After I'am done, I arrive at an expression as follows $$ \left(((a\cup b)a^*b) (ba^*b)^*a\right)^* \left(((a\cup b)a^*b) ...
1
vote
4answers
195 views

Prove this language is not regular [closed]

How do I prove that this language = {1^k | k is a perfect square} is not regular by showing that no DFA can accept the language?
1
vote
2answers
97 views

If $L_2L_1$ is accepted by a DFA, is $L_1$ too?

Given that $L_2, L_2L_1$ are accepted by a DFA, is $L_1$ accepted by a DFA too? What is the general approach to such question? What if instead of $\cdot$ we are given that $L_2 \cup L_1$ is ...
1
vote
2answers
272 views

Proving $L=\{0^n \mid \text{n is a perfect square}\}$ is not a Regular Language without the Pumping Lemma

Is this a valid way of going about proving the proposition? Let $L = \{0^n \mid \text{n is a perfect square}\}$. The regular languages are closed under concatenation. So if $x \in L, y \in L$, then ...
1
vote
2answers
282 views

regular expression

I would like to write the regular expression for the set of all binary strings where there are no three consecutive 0's. The following strings are part of the language: ...