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

learn more… | top users | synonyms

2
votes
1answer
75 views

Show a language is regular with Myhill-Nerode Theorem

I understand how to show a language is not regular using Myhill-Nerode Theorem (proof by contradiction), but how do you show the language is regular? Take language $0^*1^*$ for example. I know this ...
1
vote
1answer
26 views

Prove that the Language $L= \{ 0^n1^m \;|\; n,m \ge 0 \}$ is regular

I've looked and didn't find an answer. I know that languages like $\{ 0^n1^n \;|\; n \ge 0 \}$ and $\{ 0^n1^m \;|\; m \gt n \ge 0 \}$ are irregular so I don't understand how this language can be a ...
0
votes
1answer
168 views

How we decide for a given context free grammar generate an infinite number of strings?

Consider the following decision problems: (P1) Does a given finite state machine accept a given string? (P2) Does a given context free grammar generate an infinite number of strings? Which of the ...
1
vote
0answers
27 views

Which automata recognizes the language defined by the regular expression

I am trying to understand why the following NFA is the one which recognizes the language defined by the regular expression: $(00+10)0^*((1100+1110)0^*)^*$ As far as I can see the NFA will get stuck ...
0
votes
1answer
52 views

Design Turing Machine

Design a single-tape Turing machine with input alphabet {0, 1} to decide the language $$\{ x\in\{0,1\}^* \mid \#(0,x)=2\cdot\#(1,x)\}.$$ Could someone give me clarification on how to approach and ...
1
vote
0answers
28 views

Are languages that contain the empty string Turing-Decidable?

Given a language that is Turing-Decidable, if you add the empty string to the language then is the new language Turing-Decidable? I am very confused at this problem because from my understanding the ...
1
vote
1answer
769 views

Minimum Pumping Length

What is the minimum pumping length of (01)* The solutions says 1, but can someone explain why that is? I understand this language accepts the empty string, but the minimum pumping length cannot be 0. ...
1
vote
0answers
27 views

Intersection automaton of two automata

I need to build the intersection automaton of these two automata My attempt: My attempt is correct?
0
votes
0answers
20 views

Are languages made by splitting regular lanaguage regular?

Let's have language $L$: $L = \{u·v, u ∈ L_1, v \in L_2\}$ Lanaguage $L$ consists of words from $L_1·L_2$. We know that $L$ is regular language. In other words languages $L_1$ and $L_2$ are made by ...
0
votes
1answer
14 views

Are these two grammars similar?

Language is L = {a^nb^m | n.m >=1} Grammar 1 : S->AB B -> bB|b A-> aA|a Grammar 2 : ...
0
votes
1answer
16 views

Regular language or not : XAB where X,A belongs to (0,1)+

I am working on a problem a) L1={XAB | X,A belongs to (0,1)^+ and B is Reverse of A} i have to check whether this language is regular or not. I am trying to do ...
0
votes
1answer
37 views

Regular expression for language containing all strings that start and end with different symbols

ques - Regular expression for language containing all strings that start and end with different symbols i just went through some examples where the RE for above question is ...
0
votes
1answer
39 views

Does an NFA with a non-empty anf non-full language recognize a string with of length at most its number of states? [closed]

Let $N = (Q,\Sigma,\Delta,s,F)$ be an NFA (nondeterministic finite automaton) such that $L(N)\ne \emptyset$ and $L(N)\ne \Sigma^*$. Prove or disprove the following. $$\exists x \in L(N): ...
0
votes
1answer
59 views

Show there is a string that's length is less than or equal to the number of states in an NFA

I'm trying to prove that this is true but cannot find a good way to show this proof. The question is below: Let $T$ be an NFA such that the language defined by $T$ is neither empty nor $\Sigma^*$. ...
0
votes
2answers
251 views

Give a regular expression that generates C.

Question: In certain programming languages, comments appear between delimiters such as /# and #/. Let C be the language of all valid delimited comment strings. A member of C must begin with /# and ...
0
votes
0answers
28 views

Constructing a push down automaton

I'm having trouble constructing a PDA for the following language: $$L=\{x\#y\#z\mid x,y,z\in\{a,b\}^+\text{ with }x\approx y\text{ or }x\approx z\text{ or }y\approx z\}$$ Define $x\approx y$ as ...
1
vote
3answers
46 views

Trying to convert DFA to regular expression

I'm trying to write a regular expression from this DFA but I'm having some trouble. I can tell you what I've done so far: I started by adding a new beginning state and a new final state because ...
0
votes
2answers
26 views

Creating DFA to prove closure properties

I am given a language $L \subseteq \Sigma^*$ and symbol $a \in \Sigma$. Let $a/L= \{ w \in \Sigma^*~|~ wa \in L \}$ ex. String that end in $a$ but with that last $a$ removed. I am trying to prove that ...
2
votes
3answers
103 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
43 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
36 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
166 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
47 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
71 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
34 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
85 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
52 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
69 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
175 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
45 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
359 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
139 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
43 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
75 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
65 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. ...