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

learn more… | top users | synonyms

0
votes
0answers
8 views

Is the language $L = \{0^m1^n: m \neq n \}$ not context free?

I have been trying to prove that this is not a context free language using the pumping lemma for CFLs. I have tried for hours but am not able to prove it. Is it a context free language or not? How to ...
2
votes
2answers
31 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 ...
0
votes
0answers
6 views

DFA : if W ϵ {a,b,c}* (|w|a-|w|b+c) mod 3>=1

can you help me to solve this problem ? this is my homework and unfortunately i can't solve it , How can i design a dfa for this question ? L={ W ϵ {a,b,c}* (|w|a-|w|b+c) mod 3>=1} . . [a , b , c are ...
6
votes
1answer
289 views

Automata theory on infinite words: any video lectures?

I am fun of automata theory. Can you suggest good video lectures on the subject? (there is a good one here, but it is accessible from RWTH University only)
1
vote
2answers
20 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
2answers
55 views

Formal Languages - Regular Expression

I've been battling the following two questions for more than a day today. Write a regular expression (comprised of {a, b}) that contain at least two b and do not contain abb. Write a regular ...
0
votes
2answers
20 views

DFA Construction with three strings in language

Draw DFA that recognizes the following language, with the alphabet {0, 1} {0011, 11, 0101} I'm having a lot of trouble with this, because I know DFA have to have a determined path from each state ...
1
vote
2answers
43 views

Draw a finite state machine which will accept the regular expression $(a^2)^* + (b^3)^*$

Draw a finite state machine which will accept the regular expression: $(a^2)^* + (b^3)^*$ In particular, I am confused by the $+$ sign, what does it exactly mean? Most literature I could find about ...
0
votes
1answer
17 views

What does q-prime ($q'$) actually mean?

I'm learning about finite automata right now, and struggling with a bit of the math notation. In the explanation here: http://math.stackexchange.com/a/563875/125649, the user explains that the ...
1
vote
2answers
22 views

Is this DFA correct?

I am reviewing. I need to write a DFA that accepts a string w such that bab is not a substring. Is there any error. Also, any guideline or tips? Since it's a DFA I don't make more than 2 ...
1
vote
2answers
31 views

How to construct NFAs that recognize the following languages.

I am new to this computation theory and I am trying to answer the following question. Can you please check if I am on the right track? If there is any material that I can study for problems like ...
1
vote
3answers
27 views

Reducing a Decidability Problem to the Halting Problem

Let $L = \{(M, n): M$ halts on less than $n$ elements from a set S $\}$ I'm trying to come up with a generalization on how to solve these types of problems so I have not defined what S is. Since the ...
-1
votes
1answer
29 views

Finding the CFG (Context Free Grammar) of a language

Can we write a CFG (Context Free Grammar) for the set of all non-empty string whose length are multiple of 3 on the alphabet $ \Sigma = \{A,R,G,C\} $
1
vote
1answer
26 views

Constructing PDA for a language

I want to prove or disprove that for a given two PDA's (Pushdown Automata) $M_1$ and $M_2$, we can build a PDA $M$ such that $$L(M) = \{w \in L(M_1) \mid w\text{ contains some string in ...
0
votes
2answers
41 views

Pushdown Automata

I having trouble constructing NPDAs for these two languages: $L_1 = \{a^nb^m \mid 2n \le m \le 3n\}$ $L_2 = \{a^nb^mc^k \mid n = m \: or \: m \ne k\}$ Would these be the proper states for the first ...
5
votes
3answers
380 views

Finite Automaton that accepts only the words baa,ab, abb and no other strings longer or shorter

I am trying to understand the answer here for FA that accepts only the words baa, ab, abb and ...
0
votes
1answer
22 views

using pumping lemma to prove that a set is not regular

A={s11s|s $\epsilon$ {0}^*} so the strings 00011000 and 000001100000 are accepted of A but not 00100 or 001100000. Demon chooses k. ...
1
vote
1answer
381 views

Proof that equal-length-concatenation is a context-free language?

If A and B are languages, define A⋄B={xy | x ∈ A and y ∈ B and |x|=|y|}. For example, if A = {00, 101, 111} and B= {1, 11, 00110}, we would have A⋄B={0011}. Show that if A and B are regular, ...
8
votes
1answer
338 views

Proof that an automaton stops

I discovered an automaton that produced interesting, random-seeming patterns. The rule was as follows. Given a grid of points, some occupied and some not, and a current point and a previous point; ...
0
votes
0answers
27 views

Context-free languages

Is the following language context-free? $\{ w \in \{a,b,c\}^* : (\#_a(w) - \#_b(w)) \cdot \#_c(w) = \#_b(w)$ and all c's are encountered before any a$\}$. $\#_a(w)$ = amount of a's in w Thanks in ...
1
vote
2answers
32 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$ $\}$
3
votes
3answers
755 views

How to compute the transition function in non-determinism finite accepter NFA?

I'm currently teaching myself Automaton using Peter Linz book - An Introduction to Formal Languages and Automata 4th edition. While reading chapter 2 about NFA, I was stuck this example (page 51): ...
1
vote
4answers
138 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
1answer
38 views

Can someone explain me the proof?

I don't really understand the proof and I don't understand why it is M2 that "leads" to a reject state instead of M1.
1
vote
1answer
38 views

Can someone explain to me how this is a proof?

I honestly don't understand how this proves anything.
0
votes
1answer
31 views

How to convert this NFA to DFA?

http://www.cs.odu.edu/~toida/nerzic/390teched/regular/fa/figures/nfa-dfa1.jpg What are the steps for convert this NFA to DFA??
1
vote
0answers
28 views

Minimal DFA for a given regular expression

How can I construct a minimal DFA from the following definition? $L=\{w \in \{a,b,c\}^* $: if the second-to-last letter from w is an $a$, then the number of $c$'s $\le 1\}$ I've already made a ...
1
vote
1answer
23 views

Is there a prefix-free regular language whose set of proper prefixes is not regular

Is there a regular language $L$ such that the language $$L^\prime := \{ w : w\text{ is a proper prefix of a word in }L \}$$ has the following properties: $L^\prime$ is not regular, and $L^\prime$ ...
1
vote
1answer
22 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
votes
2answers
18 views

Regular languages properties

Define exchange($a_1$,$a_2$,...,$a_{n-1}$,$a_n$)=$a_n$$a_2$...$a_{n-1}$$a_1$ and exchange(L) = {v:v=exchange(w) for some w$\in$L} show that the family of regular language is closed under ...
2
votes
0answers
56 views

Determine the language that corresponds to the following automata.

I want to determine that language that corresponds to the following automata Note: $q_{6}$ have arrow to $a$ to himself. I started with the minimal words: $aaabb$ $aaba$ $aaaba$ $bababa$ the ...
0
votes
2answers
27 views

Find a CFG for L = { a^nb^m : n != m }

This question is upcoming for my midterm and I can't figure it out. My professor broke it down in two statements (n>m) and(m>n) and left us at that. Find a context free grammar for $L = \{ a^n b^m : ...
-1
votes
1answer
35 views

How does this language accept all palindromes with the alphabet {a,b}? [closed]

$L = \{w \in \{a,b\}^{*}$ such that $w = w^R\}$ It only says that w is the reverse of w. $L = \{ww^R \in \{a,b\}^{*}$ }$ this one says it accepts all palindromes, but the other one doesn't.
1
vote
1answer
35 views

Finite state machine

I am doing discrete math, and we are studying Finite State Machines. But i am a little confuse on how to do this. Here is a question, Write a regular expression for the language, and define a finite ...
0
votes
1answer
33 views

Prove or disprove whether the following is a regular language

I'm given the regular language L, and w being an element of L. If we remove the w from the language L, will the resulting language be still regular? Well I thought to be true. Since initially is a ...
0
votes
1answer
14 views

Eliminating Unit Productions

Eliminate all unit-productions from the grammar: $S \rightarrow abA\:|\:A\:|\:B$ $A \rightarrow B\:|\:ba\:|\:aBA$ $B \rightarrow A\:|\:aa\:|\:aA$ An article I was reading said that a unit ...
0
votes
3answers
199 views

Different version of pumping lemma and how to prove it

I have a question to solve but I am not even getting a direction to start or how to narrow down this problem. Please provide in your inputs. Consider the following version of pumping lemma. For any ...
0
votes
1answer
17 views

Are these two languages equivalent?

$L = \{w \in \{a,b\}^{*}$ such that $w = R(w)\}$ R(w) = the reverse of w $L = \{u \in \{a,b\}^{*}\}$ If not can you draw a pda or define a grammar for each? I don't see how they could have ...
1
vote
2answers
85 views

Euclid's Proof that there are an infinite number of primes

I'm trying to clarify my understanding of decidability of a language. The following question is totally made up by me so I hope it makes sense. Let $L = \{A: A \text{ is an algorithm that can ...
0
votes
0answers
8 views

how to convert Finite Automata into Push Down Automata

I am trying to convert Finite Automata into Push Down Automata and I am not sure if I am doing this right. There are not many good tutorials on this topic that I can find, but this is what I have. I ...
0
votes
0answers
10 views

Cartesian product of a DFA and PDA

I am just wondering how to do it. I am not quite sure if this is the right way. 1) Write down all the combination of states. 2) Take into consideration the "input" side of the DFA and write the ...
0
votes
2answers
21 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
1answer
16 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 ...
0
votes
0answers
15 views

Designing a pushdown automata

I think I realized something, but I am not sure. So what I think I've realized is that if you have to design a L such that it accepts any string with the same amount of 1 and 0. You need 2 states: ...
0
votes
3answers
58 views

the difference between regex operations (math) and regex (unix/linux)

what is the difference between regular expression operations (union, concatenation, kleene star) and regular expression (implemented in UNIX and can be used together with the grep command)? Are there ...
4
votes
2answers
98 views

Have action/predicate systems (or similar) been considered in the literature?

Question. Has the following concept, or anything similar, been considered in the literature? Definition. An action/predicate system consists of sets $A$ (the actions) and $X$ (the predicates) such ...
0
votes
1answer
36 views

Prove or disprove that the language $L_1 = \{a^nb^m \mid n < m \}$ is regular

I have possible strategy for a proof that it is not regular. I am wondering if it is valid. Step 1: Prove that the language $L_2 = \{a^nb^n\}$ is not regular (for example with the Pumping Lemma). ...
2
votes
0answers
50 views

This proof in my textbook involving the pumping lemma appears incorrect - is it?

It states Let $B$ be the language $\{0^n1^n2^n | n \geq 0\}$. We use the pumping lemma to prove that $B$ is not regular. The proof is by contradiction. Assume to the contrary that $B$ is regular. ...
0
votes
1answer
18 views

Prove L is not a regular language (A Finite State Automaton cannot accept it)

$$\mathscr L = \{x \in \{0,1\}^* \mid \text{there is a } y \in \{0,1\}^* \text{ such that } x = yy\}$$ How can I prove that this is not a Regular language? I tried using proof by contradiction but ...
1
vote
1answer
34 views

How to construct a grammar G such that L(G)={x^ny^mx^my^n/m,n>1}?

construct a grammar $G$ such that $L(G)=\{x^ny^mx^my^n/m,n>1\}$? I don't have much idea how to approach this one. Could some help me to understand how to approach these kinds of problem?