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

learn more… | top users | synonyms

1
vote
2answers
318 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
4answers
179 views

Non-Deterministic Turing Machine Algorithm

I'm having trouble with this question: Write a simple program/algorithm for a nondeterministic Turing machine that accepts the language: $$ L = \left\{\left. xw w^R y \right| x,y,w \in \{a,b\}^+, ...
1
vote
3answers
1k views

Is indistinguishability an equivalence relation?

Let x and y be strings and let L be any language. We say that x and y are distinguishable by L if some string z exists whereby exactly one of the strings xz and yz is a member of L; otherwise, ...
1
vote
2answers
69 views

Why this lemma is true?

Let $\Sigma$ be an alphabet of size $|\Sigma|=k$. Let $w\in\Sigma^*$ be a word over $\Sigma$. If $|w| > 2^k$, then $w$ contains an infix $y$ with $|y|\ge 2$, such that every letter occurring in y ...
1
vote
2answers
280 views

Is this DFA correct

I'm supposed to construct a DFA which accepts { w | w is a word except 'aa' and 'aaa' } Is this the correct solution? The thick line state is supposed to be the end state. EDIT Sry, somehow ...
1
vote
2answers
176 views

Convert NFA with only accepting states to regular expression?

Suppose you wanted to find a Regular Expression that defines the language accepted by the folowing Finite State Automaton. Where S1 and S2 are both accepting states. How would I go on doing this?
1
vote
3answers
121 views

CFG for language l

please solve this question.thanks Consider the language L expressed by (a+b)*a defined over Σ = {a, b}. Draw FA and construct the CFG corresponding to the language L.
1
vote
2answers
459 views

Constructing a finite automata from a subset of its language

I am attempting to solve the following problem: Let $M=(Q,\Sigma,\delta,q_0,F)$ be a deterministic finite automata which accepts $L(M)$, and let $E$ be the subset of $L(M)$ consisting of all words of ...
1
vote
1answer
57 views

Question about deterministic finite automaton and accepting states

For $n \in \mathbb N$, an "$n-$DFA" is an automaton with exactly $n$ accepting states. Let $\Sigma=\{0,1\}$. Prove that the set of the languages that can be accepted by "$1-$DFA" is a subset of the ...
1
vote
2answers
38 views

Is $L_1 = \{w ∈ {0,1}∗ | \text{w has at least as many occurrences of (110)’s as (011)’s}\}$ regular?

Let $L_1 = \{w ∈ \{0,1\}^∗ | \text{w has at least as many occurrences of (110)’s as (011)’s}\}$. Let $L_2=\{w ∈ \{0,1\}^∗ | \text{ w has at least as many ...
1
vote
3answers
70 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
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?
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
1answer
60 views

Write the regular expression of the language that the DFA accepts.

I am given a DFA and I have tried to write the regular expression of the language that it accepts. This is the DFA that I am given: I have found some words that the DFA accepts: ...
1
vote
2answers
68 views

How to break down a problem while constructing a CFG for a language?

A problem I came across was: Design a CFG for the language $\{a^ib^jc^k\,|\,i=j+k \}$ The solution I came up with : $S\rightarrow aSc\,|\,S_1$ $S\rightarrow aS_1b\,|\,\epsilon$ It took ...
1
vote
2answers
29 views

Regular expression translation.

Given a set {1,2,...9} how can I construct a regular expression starts with a 3 has no 8's and has even number of 6's? Here's what I tried: $$$$ Define a new set no8 = {1,2,3,4,5,6,7,9} ...
1
vote
2answers
263 views

The halting problem for tapes that are or are not completely blank

Is it possible to construct a Turing machine that halts only if the tape is not completely blank? Also, is it possible to construct one to halt if the tape is completely blank? Intuitively, I think ...
1
vote
3answers
314 views

NFA for $(ab|a)^{*}$ using only 2 states

In Introduction to the Theory of Computation by Michael Sipser, there's an example which shows how to convert the regular expression $ (ab|a)^{*}$ into an NFA. The "standard" method results in 8 ...
1
vote
1answer
122 views

Grammar outside the Chomsky Hierarchy

This grammar describes a language that may fall outside the Chomsky Hierarchy (CH): \begin{array}{l} S \to abAbba \\ A \to abA \mid bbaB \\ B \to aab \\ \lambda \to Aab \mid aB \\ \end{array} Going ...
1
vote
1answer
77 views

Infinite regular languages

There is a formal proof for the following sentence? For every 2 languages $A,B$, we write A@B if A subset of B and B\A infinite. Prove that if $A,B$ regular languages and A@b, than exists regular ...
1
vote
2answers
37 views

Construct a deterministic finite automation

The question asks to: construct a DFA which accepts exactly $\frac{n(n-1)(n-2)}{6} + \frac{n(n-1)}{2}+1$ many members of $\{0, 1\}^n$ for every n. I have no idea where to start to constructing the ...
1
vote
2answers
3k views

Concatenation of 2 finite Automata

I have some problems understanding the algorithm of concatenation of two NFAs. For example: How to concatenate A1 and A2? A1: ...
1
vote
2answers
290 views

Prove that any finite set of words is regular. How many states is sufficient for a single word $w_1…w_m$?

DFA Prove that any finite set of words is regular. How many states is sufficient for a single word $w_1...w_m$? For part 2, wouldn't it require M states if the word length is M?
1
vote
1answer
125 views

Is the language $\{i|f(i)=1\}$ recursive, function $f$ is described further inside. [duplicate]

Possible Duplicate: Show $f$ is primitive recursive, where $f(n) = 1$ if the decimal expansion of $\pi$ contains $n$ consecutive $5$'s $$L = \{i\mid f(i)=1\}$$ $f(i)$ equals $1$ if ...
1
vote
1answer
462 views

A regular expression for the words that don't contain the sequence $ab$ over $\{a,b,c\}$

The following is an exercise in a book I am reading: Let $\Sigma=\{a,b,c\}$, define $L$ to be the language of all words over $\Sigma$ that do not contain $ab$ as a sub-word. Find a regular ...
1
vote
1answer
38 views

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

I need to find and to prove (by the pumping lemma or by building a grammar) if $L=\{o^{i}1^{i}o^{j}1^{i} | i,j>0\}$ is a context free language. I would like to get some help. thanks!
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 ...
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 ...
1
vote
1answer
406 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
vote
2answers
53 views

Why |w|>=m in pumping lemma?

If L is a regular language, then there exists a constant n (which depends on L) such that ...
1
vote
1answer
47 views

Regular expressions

I have this assignment and I have to prove that $$ (b+aa^* b)+(b+aa^* b)(a+ba^* b)^* (a+ba^* b) = a^* b(a+ba^* a)b^* $$ How do I prove this? What I have is this: $$\begin{align} \text{LHS} ...
1
vote
3answers
56 views

Show that a language is regular

Show that language $B$ is regular: $$B = \left\{1^ky\mid y\in \{0,1\}^*\right\} $$ $y$ contains $\ge k$ symbols $1$ So I try in following way - I'll draw DFA: What about my solution? Is it good?
1
vote
2answers
45 views

Did I find the right expression for the regular language for this FSA?

I have the following FSA, and the regular language that I found for it: Is this language correct? It doesn't match the solution in the book, but my teacher says there can be multiple equally ...
1
vote
2answers
37 views

FSM to be regular with atleast two 0's and at most two 1's

Is it possible to construct a FSM to prove that the set $X$ is regular, where $$ X = \{s \in \{0,1\}^* \mid \text{$s$ contains at least two $0$'s and at most two $1$'s}\}\ ? $$
1
vote
1answer
43 views

Can someone explain to me how this is a proof?

I honestly don't understand how this proves anything.
1
vote
2answers
50 views

Closed regular languages

Are regular languages closed under the following construction? $f(L) = \{w \mid w \in L$ and for all prefixes $x$ of $w$ it holds that $x \notin L$ $\}$
1
vote
1answer
31 views

Subset of regular languages

Assume $L_1$ and $L_2$ two regular languages, and $L_1\subseteq L\subseteq L_2$. Does this imply that $L$ is a regular language? Thanks in advance.
1
vote
2answers
72 views

New automaton that runs two others step by step?

If I have two automatons for two languages ($M_1, M_2, L_1,L_2$ respectively), what would be the procedure to mix them by defining a new automaton such that the new automaton would accept the words ...
1
vote
2answers
62 views

If $v^6w^8 = w^{12}v^4$ then $(vw)^2 = v^2w^2$?

Given the words $v,w \in \sum^*$, is this correct? If $v^6w^8 = w^{12}v^4$ then $(vw)^2 = v^2w^2$ If $vw^2 = wv^2$ then $v=w$ For one, I tried $v=\epsilon, w=\epsilon$ and it worked, and ...
1
vote
2answers
171 views

Whether $L=\{(a^m,a^n)\}^*$ is regular or not?

I am condidering the automatic structure for Baumslag-Solitar semigroups. And I have a question. For any $m,n \in Z$, whether the set $L=\{(a^m,a^n)\}^*$ is regular or not. Here a set is regular means ...
1
vote
1answer
979 views

How to prove CYK algorithm has $O(n^3)$ running time

I have a final coming up in few days, and the professor mentioned the CYK algorithm. I want to be prepared for the final. I'm trying to find out how to prove the algorithm has worst case running time ...
1
vote
2answers
969 views

Showing that a language is regular - Pushdown Automaton

So what I have to prove is that $L$ is regular given that the stack of PDA for $L$ never grows beyond $n$ entries on any input, and in this case $n=200$.
1
vote
2answers
170 views

Solve right linear set equations

Trying to solve this set of equations. I'm feeling like I'm making it so complicated. Of course + is union. Am I on the right track? A = 0B + 1D B = 0C + 1A C = 0A + 1B + λ D = OD + 1C + λ A ...
1
vote
2answers
1k views

Can _any_ NFA be converted to a DFA?

I was wondering if for every NFA there exists an equivalent DFA? I think the answer is yes. How would one prove it? Since I'm just starting up learning about Automata I'm not confused about this and ...
1
vote
2answers
230 views

Pushdown Automaton

Can someone help me construct a pushdown automaton to recognize the following regular expression representing the language $(a^3+a^5)$* using as few states as possible? How can this be done using a ...
1
vote
1answer
91 views

Show that $a^k w b^k$ when $|w|_a$ is divisible by $3$ is not regular

I want to show that $L = \{ a^k w b^k \mid k \geq 0, w \in \{a,b\}^*, |w|_a \text{is divisible by } 3 \}$ is not regular. I tried to use Pumping lemma as follows: Let $p$ be pumping length. $a^pb^p ...
1
vote
1answer
54 views

what is the effect of adding another stack to a PDA

does it increase the power of a push down automata? or does it have no effect on the power of the PDA ?
1
vote
1answer
204 views

Finite Automata, basic question with semigroups

If we use the notation where when we say: $$M = M(G)$$ We mean to say that $M$ is a automata with states and alphabet elements of $G$. From here, I am posed this question (Abstract Algebra by ...
1
vote
1answer
188 views

CFG pumping lemma

I can't figure out how to prove this is a non CFG. $\{xy : x, y \in \{a,b\}^*, n_a(x) = n_a(y), n_b(x) = n_b(y) \}$, Where the number of a's in x = number of a's in y and number of b's in x = to the ...
1
vote
1answer
43 views

How to check if a language is regular

I'm currently studying a formal languages & automate module on my course and I have been asked to answer the following question: Which of the languages below are regular? If the language is ...