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

learn more… | top users | synonyms

1
vote
2answers
59 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
2answers
100 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 ...
1
vote
3answers
185 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 ...
1
vote
3answers
93 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
58 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
42 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
65 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 ...
1
vote
2answers
30 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}\}\ ? $$
0
votes
1answer
36 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
4answers
169 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
44 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
42 views

Can someone explain to me how this is a proof?

I honestly don't understand how this proves anything.
1
vote
2answers
43 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$ $\}$
0
votes
1answer
200 views

How to convert this NFA to DFA?

What are the steps for converting this NFA to a DFA??
1
vote
0answers
62 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 ...
0
votes
0answers
35 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
1answer
77 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
25 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.
2
votes
1answer
79 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 ...
-1
votes
2answers
511 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
194 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
489 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 ...
1
vote
1answer
115 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
26 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
1answer
23 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
108 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 ...
1
vote
2answers
92 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?
2
votes
1answer
70 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
3answers
183 views

What is the difference between regex operations in math and regex in 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 ...
0
votes
1answer
90 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). ...
0
votes
1answer
45 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 ...
0
votes
0answers
38 views

Is this grammar ambiguous?

$S > SS|10|0$ $S > SS > SSS > 0SS > 00S > 000$ $S > SS > 0S > 0SS > 00S > 000$ $2$ leftmost derivations
1
vote
1answer
52 views

Checking some Regular Expression problems

I'm given the alphabet $$ \Sigma = {\{a,b}\} $$ I tried to write a regular expressions for presenting the following sets: All strings in $$\Sigma ^ *$$ with: a-) number of 2s divisible by 4 b-) ...
0
votes
1answer
61 views

Using the Pumping Lemma to prove a language is not regular.

I want to know if my proof is wrong and whether what I am doing works. $$\sigma = \{0, 1\}$$ $$A = \{0^n1^m \mid n < m\}$$ Claim: A is not regular. Proof: Assume A is regular. Let p be the ...
1
vote
1answer
25 views

How to prove the following related with regular languages

How can we prove the following. If $$\sum$$ is any alphabet and L is any language $$L \subset \sum*$$ Then L*L* = L* ?
1
vote
2answers
72 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 ...
8
votes
1answer
359 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
1answer
33 views

Question about Notation in a Regular Language

I am a little confused about the following notation: $L' = \{xy|x\in L \ , y\in L^R\}$. I think this expression is not equivalent with palindrome but I am not entirely sure. For example, I think the ...
0
votes
2answers
34 views

Proof that suffix of $ab$ needs at least 3 states in NFA

I need to prove that for an NFA that accepts all languages $L(M)=\{w \in \{a,b\}^* \mid wab \}$ with a suffix of $ab$ needs at least 3 states. The smallest automata would look like this: $\to(s) \to ...
0
votes
1answer
49 views

Proving that a language having a particular CFG grammar is equivalent to a particular L

I think we need to prove that L(G) is a subset of L and then we need to prove that L is a subset of L(G). For the first part, I think we need to say for any w in L(G) we have an even number of as ...
1
vote
1answer
41 views

Particular Problem for Context Free Grammars

Consider the context-free-grammar $G$ defined by productions: $$ S \rightarrow aS\,|\,Sb\,|\,a\,| b $$ Prove by induction on the string length that no string in $L(G)$ has $ba$ as a substring. I ...
2
votes
1answer
43 views

Equivalence of two regular expression

I have a quick question to ask. So I am trying to come up with a regular epxression which represent a language over {a,b} that contains at least one 'b' in it. I came up with this: $$(a| b)^*b(a| ...
0
votes
1answer
32 views

Create a general NFA for $M_n$

I need to create a general NFA $M_n$ where $n \in \mathbb{N_0}$ with the following language defined: $$L(M_n) = \left\{ w \in \{0,1\}^* \big | x1y \textit{ for } x \in \{0,1\}^* \textit{ and } y \in ...
0
votes
1answer
145 views

find a regular expression and FA that each define L1 ∩ L2

from the following pairs I am trying to find a regular expression and FA that each define ...
5
votes
3answers
1k 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
29 views

How can I show ithat a language is regular?

I have a very quick question about regular languages, I think $\{a^{2n}| n\geq 1\}$ is regular. I do know that pumping lemma can be used to show something that is not regular. I am wondering what ...
0
votes
1answer
39 views

Question About Pumping Lemma used on a FA

I am learning about pumping lemma and I am trying to solve a problem. I need to use pumping lemma to show that: the Language L(M) defined by the following machine is infinite. Here is the dfa: ...
3
votes
0answers
76 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. ...
3
votes
3answers
81 views

Is $L = \{(x,y,z) | x+y=z\}$ a regular language?

Suppose $x,y,z$ are coded as decimal or their binary representations in an appropriate DFA. Is $L$ regular? My intuition tells me that the answer is no, because there are infinitely many combinations ...
2
votes
1answer
931 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 ...