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

learn more… | top users | synonyms

0
votes
1answer
34 views

proving that a regular language can be accepted by a fast finite automaton

Let it be L a regular language. Prove that exists a fast finite automaton (FFA) M which excepts L. Definition of FFA: FFA is a 6-tuple M=$<Q,Σ,P,δ,s,A>$ which: 1. Q is a finite set of ...
4
votes
2answers
49 views

proving that $L_\text{almost}$ is a regular language

Let it be L, a regular language. we will define: $L_\text{almost} = \{ w'\mid \exists w\in L\ w' \text{ is almost similar to }w \}$ a word $w'$ is almost similar to $w$ if they are in the same ...
0
votes
1answer
15 views

If $L_1$ and $L_2$ are non regular then $L_1 \cup\;L_2\; = L$ can be regular?

I need to prove or disprove with contrast example: If $L_1$ and $L_2$ are non regular then $L_1 \cup\;L_2\; = L$ can be regular I have no idea how to begin, hints and spoilers are welcomed
0
votes
1answer
27 views

DCFL are closed under Intersection with Regular Languages?

Let $L_1$ be a regular language, $L_2$ be a deterministic context-free language and $L_3$ a recursively enumerable, but not recursive, language. Which one of the following statements is false? $L_1 ...
0
votes
1answer
24 views

$L=\left\{ s \in (0+1)^* \mid \text{ for every prefix s' of s,} \mid n_{0}(s')-n_{1}(s') \mid \leq 2 \right \}$ is regular?

Given language : $L=\left\{ s \in (0+1)^* \mid \text{ for every prefix s' of s,} \mid n_{0}(s')-n_{1}(s') \mid \leq 2 \right \}$ is regular? Somewhere it explained as : Here we need just 6 states ...
0
votes
0answers
27 views

If the strings of a language L can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true?

(A) L is Regular (b) L is context free but not necessarily Regular (c) L is recursive but not necessarily Regular (d) L is recursively enumerable but not necessarily Recursive I could only conclude ...
1
vote
1answer
115 views

Automata | Prove that if $L$ is regular than $half(L)$ is regular too

I've see couple of approaches to this kind of questions yet I have no clue how to approach this one. Let L be regular language, and let half(L) be: $half(L) = \{u | uv \in L\ s.t. |u|=|v|\}$ Prove ...
0
votes
1answer
16 views

Show that the problem of deciding whether a Turing machine prints something is undecidable

I am unable to get the logic for showing that the problem of whether a Turing machine prints something is undecidable by showing that the halting problem reduces to it. Please guide me with this.
0
votes
2answers
27 views

difference between A* and 2^A*

let A be any input alphabet then what is the difference between A* (kleen closure of A) and 2^A* ?
0
votes
1answer
56 views

If a language is context free ,then why is the complement of the language recursively enumerable?

If a language is CFL , then it is clearly recursive and if it is recursive then it is obviously recursively enumerable but then recursively enumerable languages are not closed under complement so how ...
0
votes
0answers
43 views

Construct an NPDA for the following language: L = {a^nb^m | n>= 0, n!= m}

How we've learned is to first construct a CFG, and then use that to construct the npda. Our end goal is a transition graph. The language is $L = ${${a^nb^m | n>= 0, n!=m}$} We can think of ...
1
vote
1answer
46 views

what are the practical uses of “game of life” or “langton's Ant”

A few questions: Besides looking really cool, what are the practical uses of "game of life" or "langton's Ant"? I understand how agent-based modeling itself is a potentially useful methodoly, not ...
1
vote
0answers
23 views

why is automaton with a queue is more powerful than an automaton with a stack?

what is the logic behind this statement that with the use of queue the automaton becomes more powerful , is it that in a queue , we may do operations from both the ends as compared to a stack so it is ...
2
votes
0answers
52 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)*. ...
0
votes
0answers
14 views

Question on Regular Language

L={a^($2^n$),n>1} $U$ {$a^m$,m>1} Is L a regular? My approach is-- union of a non regular and regular language may be regular or may be not regular. The left side of union is not regular so the ...
0
votes
0answers
17 views

what is the minimum no of DFA states required to recognise below language?

$L=\{a^nk , k>0 \text{ and } n \text{ is an integer constant} \}$ In this question which constant should be changed , n or k while considering the DFA since then it can be either $n+1$ or $k+1$ ?
1
vote
2answers
41 views

Prove that $\{w \mid \text{ w has even length and the first half of w has more 0s than the second half of w} \}$ is not regular?

I have had some difficulties understanding proofs that a language is not regular using the Pumping Lemma, and now I need to prove that the following language $$A = \{w \mid \text{ w has even length ...
0
votes
1answer
30 views

Understanding the proof that uses Pumping Lemma that the language $C =\{w \mid w$ has an equal number of $0$'s and $1$'s$\}$ is not regular

I have just started reading about the Pumping Lemma, and I have some difficulties understanding the proofs of non-regularity of languages. For example, in the book I am reading there's a proof for ...
0
votes
2answers
19 views

Intersection of two languages

Let $L=L_1∩L_2$, where $L_1$ and $L_2$ are languages as defined below: $L_1=\{a^mb^mca^nb^m∣m,n≥0\}$ $L_2=\{a^ib^jc^k∣i,j,k≥0\}$ Then $L$ is Not recursive Regular Context free but not regular ...
1
vote
0answers
46 views

Evaluating $b^*a^*\cap a^*b^*$ to a minimal regular expression

Evaluate to a minimal expression: $b^*a^*\cap a^*b^*$ To me, the only elements to both sets are the empty string, strings containing only $a$, and strings containing only $b$, so isn't the ...
1
vote
0answers
62 views

The set of all strings with twice as many 0's as 1's

I have to create a PDA that accepts strings with twice as many 0's as 1's. So far I have decided to create one which accepts via empty state: (q0, 0, Z0) - (q1, 0) (q0, 1, Z0) - (q1, 11) (q1, 1, ...
1
vote
1answer
31 views

Prove the infinite union is not regular

Prove $\bigcup _{i=1}^\infty A_i$ is not regular. We know $A_i$ is regular, but how can prove the infinite union is not regular. I think a counter example would work, but I can't think of any. ...
2
votes
1answer
51 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
22 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
112 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
25 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
0answers
31 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
24 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
185 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
24 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
16 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
15 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
28 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 ...
1
vote
1answer
24 views

Finding a language accepted by an automaton?

I'm currently doing work on discrete mathematics in my free time and am having some difficulties with understanding some questions pertaining to Automata and Finite-state machines. To be specific, I'm ...
0
votes
1answer
36 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
26 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
143 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
27 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
2answers
37 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
90 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
25 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
20 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
38 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
32 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
105 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
26 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
43 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
21 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 ...