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

learn more… | top users | synonyms

0
votes
1answer
20 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
22 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: ...
0
votes
2answers
72 views

Show that, given regular expression $R$, we can decide whether $L(R)$ is prefix-free

Suppose language $L$ is called prefix-free if no member is a proper prefix of another. For instance, cat is a proper prefix of category and so $L = \{cat,category,ego,go,rye\}$ is not prefix free. ...
0
votes
1answer
27 views

Creating a Push Down Automaton from a Grammar

I have the following grammar, but I'm not sure what exactly it is that it does: $\qquad\begin{align} S &\to S \vee T \mid T \\ T &\to T \wedge F \mid F \\ F &\to p \mid \thicksim p ...
0
votes
2answers
42 views

Proof by pumping lemma

Let's say that we have to prove that $L = \{ww^Rv |w,v\in \Sigma^*\}$ is irregular. I would take a string such that $w = baba^m$ and $w^R=a^mbab$ and $v = a$ and then I would pump divide $w$ into ...
0
votes
2answers
208 views

Regular expression and DFA/NFA questions

If a language L is generated by a regular expression, then L is recognized by a DFA. I think this is true, because regular expressions describe regular languages, those of which are exactly ...
0
votes
1answer
19 views

Reversed Language of a Non Regular Language

Is the following saying true or false? In any case why? Thanks!
0
votes
3answers
20 views

If $s \geq 3$, $3$ divides $s$, and $t = s/3$, then $t+1 < s$.

I am using the pumping lemma to prove a language is not regular, and would like to assert what I have stated in the title of the question to complete my proof. That is, if $s \geq 3$, $3$ divides $s$, ...
0
votes
1answer
57 views

Finding regular expressions

I'm given the DFA shown below and need to find regular expressions for the following languages: $L_{1,2}^0, L_{2,1}^6, L_{2,5}^4, L_{2,3}^5, L_{1,3}^5$. The language $L_{p,q}^r$ is defined as ...
0
votes
1answer
31 views

Help Specify possible definitions for this Boolean Function

My math is rusty, but I need some guidance here. Problem I wish to design a stochastic, boolean procedure $f(state)$, that picks a winner, $f(state_{win})\to 1$ or loser, $f(state_{loss})\to 0$. I ...
0
votes
2answers
77 views

What is the language generated by G and how to draw the finite state automaton that recognizes this language?

G = (V, T, S, P) V = (0, 1, A, B, S) T = {0, 1} S is start S -> 0A S -> 1A A -> 0B B -> 1A B -> 1 For the drawing, I am confused about the last ...
0
votes
1answer
75 views

unrestricted grammar and Turing machines

Let $G$ be an unrestricted grammar. Then the problem of determining whether or not $L(G) = ∅$ is undecidable. Let $M_1$ and $M_2$ be two arbitrary Turing machines. Show that the problem $L(M_1) ⊆ ...
0
votes
1answer
74 views

DFA with $k$ states, words of length $k$

Is this statement true? If we have a DFA with $k$ states, and if $L(M) = L$ is infinite, then there is a word of length at least $k$ and at most $2k-1$. Isn't this a trivial answer? Take the ...
0
votes
1answer
56 views

Converting NFA to DFA

Im trying to convert a NFA to DFA. This is the NFA and this is the DFA to which i converted Is this right? Also when converting if i write a state as [q0,q1] is this same as [q1,q0] edit: ...
0
votes
1answer
46 views

Proving Equivalence of DFA and NFA

Im trying to learn Equivalence of DFA and NFA.The problem is that in the below explanation Q' is given as the power set of Q.But this statement seems to be contradictory to the previous statement ...
0
votes
1answer
15 views

How is Finite Automation Linked to Lexical Analyser

I understand that Finite Automaton is a Mathematical model of a system with discrete number of input and outputs. Also the system has finite number of states.My question is how is this linked with ...
0
votes
1answer
53 views

Designing PDAs to Accept Languages

I want to design PDAs to accept the following two languages: $L_1 = \{a^ib^jc^k \mid i=j \text{ or } j=k\}$ $L_2 = $ The set of all strings with twice as many $0$s as $1$s. I am especially ...
0
votes
1answer
58 views

Prove/Disprove: $vwvw=vvww$ iff $\{v\}^*\{w\}^*=\{vw\}^*$

Let $\Sigma$ be an alphabet and $v,w\in \Sigma^*$. I'm trying to prove that: $$vwvw=vvww\quad\text{iff}\quad\{v\}^*\{w\}^*=\{vw\}^*.$$ I tried to do it by induction, with no success. Any help will ...
0
votes
1answer
30 views

Grammar derivation

Given these grammar productions: $$\begin{align*} &S\to A1B\\ &A\to 0A\mid\lambda\\ &B\to 0B\mid 1B\mid\lambda \end{align*}$$ And given string $w = 01101$ If I wanted to make a) ...
0
votes
1answer
30 views

S-grammar for this regular expression

Given this regular expression: $r = a a^* b + b^* c b$ I think this is the simple grammar, but I was getting a little lost with the productions: $S \rightarrow S_1 | S_2$ $S_1 \rightarrow a A b$ ...
0
votes
1answer
100 views

Proving that $L= \{a^nb^n, n\ge 0\}$ is not a regular language.

The questions i'm 'stuck' on is: Let $\Sigma = \{0,1,2\}$ be the alphabet, and let $L$ be the collection of all the languages that contains only words that have even length. Prove that there are ...
0
votes
2answers
21 views

Regular Language Operation

I need to show that the given regular language is closed under the following operation. For example: AllSuffixes(L) = {v : uv in L for some u in (0+1)* } I do not ...
0
votes
2answers
70 views

Can someone explain this automaton?

I have a question about constructing an automaton for given language: $$L = \{000, 010, 100, 110\}$$ Solution for this was given below. Can anyone explain why this automaton accepts the language? This ...
0
votes
2answers
120 views

Is it true that any infinite subset of a non-regular unary language is non-regular?

My question is very similar to this: Is there a subset of a non regular language that is regular My claim is that because the subset is infinite, Myhill Nerode says that the language is not regular. ...
0
votes
2answers
97 views

Pumping Lemma to show a language is not regular

Let $\Sigma = \{a, b\}$. Use the Pumping Lemma to show that $\mathcal L = \{ a^pab^q: p < q \}$ is not regular. Not sure how to apply PL here, if someone can give some direction.
0
votes
1answer
93 views

Right-linear grammar from regular expression

I made a right-linear grammar that from this regular expression: The alphabet is: $Σ = \{a, b, c\} $ Regular expression: $r = cc^*(ba)^*bb$ My solution, it seems a little too short like I'm ...
0
votes
1answer
24 views

Language made by a regular expression

I created a language from this regular expression but I'm not sure about it, especially where I wanted to use the $w$ to express a sequence of terminals. The expression: $r = a a ^{*} (b + bb + bbb) ...
0
votes
1answer
47 views

Constructing a parallel composition from a given transition system and automaton

I am looking at an exercise, where it asks me to construct a parallel composition from a given transition system and an automaton. The transition system looks like this: and the automaton (with ...
0
votes
2answers
192 views

Finite automata for any even number of a's followed by any even number of b's

I'm new to formal languages. I'm stuck with the following question. Any help is appreciated. Find finite automata for $$L = \{a^i b^j \mid i, j\text{ are even, }j\ge0\}$$ Thank you
0
votes
1answer
183 views

Does closure under the union and concatenation operations imply closure under the star operation?

Given any two languages $A$ and $B$, recall the following regular operations: Union: $A \cup B = \{x \mid x \in A \text{ or } x \in B\}$ Concatenation: $A \circ B = \{xy \mid x \in A \text{ ...
0
votes
1answer
57 views

The Relation of Cellular Automata to Languages

In Conway's Game of Life, would a cell be considered a deterministic finite automata? Is there a language for the automata, and would it be a regular language? In probabilistic cellular automata, are ...
0
votes
2answers
346 views

To design a Finite State machine

Design a FSM for a binary number in which the input is valid if no. of 0's divisible by 5 and no. of 1's divisible by 3
0
votes
1answer
151 views

Is this language regular?

Given $m,n∈Z$, A is a finite alphabet set ,and $L=\{(a^m,a^n)\}^*$ is subset of $A^*\times A^*$ . Is this language regular ? For example, is $L=\{(a^3,a^7)\}^*$ regular ? Here L is not the set ...
0
votes
2answers
107 views

Prove $L=\{ 1^n| n\hspace{2mm}\text{is a prime number} \}$ is not regular.

Prove $L=\{ 1^n| n\hspace{2mm}\text{is a prime number} \}$ is not regular. It seems to use one Lemma: Pumping Lemma.
0
votes
1answer
40 views

Given a DFA $\mathcal{M} = (S, \Sigma, q_0, \delta, F)$, is there an algorithm that finds the pumping length of $L(\mathcal{M}$)?

This question has been bugging me for a while, and I'm curious what such an algorithm would look like, if it exists. My guess is that it does exist, but I'm not sure how it would look.
0
votes
1answer
228 views

Describe a Turing Machine that accepts the language of all non-negative decimal integers that are multiples of 3.

I have exam coming up and I need help with this: Describe a Turing Machine that accepts the language of all non-negative decimal integers that are multiples of 3 Thank you :)
0
votes
1answer
294 views

Turing Machine Variation

Hi i'm trying to figure out this question: Give a formal definition of multihead-multitape Turing machine. Then show how such a machine can be simulated by a standard Turing machine Can someone ...
0
votes
1answer
48 views

How can I prove a DFA accepts a certain mininum number of states?

We know that if there are two languages, L1 and L2, if L1 and L2 are regular, the intersection of those two is also regular. Suppose we have two machines, M1 and M2, and using them, a new machine M3 ...
0
votes
1answer
41 views

Büchi Pushdown System Accepting Run

From the following definitions: Definition (Büchi Pushdown System) A Buchi pushdown system (BPDS) is a tuple BP = (Q,S,→,Qf) with (Q,S,→) a PDS (where S is the stack content) and Qf ⊆ Q a set of fi ...
0
votes
1answer
77 views

L is a context free language over {0, 1}, prove, disprove:

cont... L is a context free language over {0, 1}, prove, disprove: L1 is a CFL over {a, b}, where L1 is the language of all words from L, that 0 is converted to a and 1 is converted to bba. Thanks ...
0
votes
1answer
87 views

Prove min(L) = all words in L that they don't have any prefix of themselves in L

We define the minimal words language of $L, \min(L)$, to be the language of all words in $L$ that don't have any prefix in $L$. Assume $L$ is regular language. I need to prove by building an ...
0
votes
2answers
265 views

Proof Two Grammars Generate the Same Language

I have two right linear grammars and I need to prove they both generate the same language. What is the right way to do it? L1: $S \rightarrow 0A$ $S \rightarrow 1B$ $A \rightarrow 0A$ $A ...
0
votes
1answer
285 views

Creating a minimal dfa from a regular expression

Having a bit of difficult with the following question: Create a minimal dfa for the language $L(r)$ where $r = a^*\bigl((ab+b)^*\bigr)$?
0
votes
1answer
145 views

Proving that for every context-free language there exist a pushdown automata $M$ s.t. $L=L_{e}(M)$

The book I am reading have proof for the statement Every context-free language there exist a pushdown automata $M$ s.t. $L=L_{e}(M)$ For the case $\epsilon\not\in L$. The proof uses greibach ...
0
votes
1answer
132 views

Proof related to a finite state machine

I have this confusion related to a finite state machine M such that if the number of states n>=2, then there exits i $ \overset{i}\equiv{}= {\overset{i+1}\equiv{}}$ I mean the $i^{th}$ equivalence ...
0
votes
1answer
72 views

Regular expression arithmetics

What are the rules of regular expression arithmetics ? For example: Let $\Sigma=\{0,1\}$ $1. 1+01=(\epsilon+0)1$. $2. (\epsilon+00)^*=(00)^*$
0
votes
1answer
97 views

Help with set notation?

I want to describe the set of all words in the following format: a0w1 where a represents EITHER 0 or 1, and w represents {0,1}* So 00011 is valid as is 1010011, etc. etc. I'm really new to set ...
0
votes
1answer
75 views

something that looks sort of symmetrical but also not

Given the set $S_0$ of finite binary strings whose digit sum is congruent to 0 mod 2 and the set $S_1$ of finite binary strings whose digit sum is congruent to 1 mod 2, what are the implications of ...
0
votes
1answer
60 views

Modelchecking on Automata, $\phi$ not SAT and $\phi \models$ False

Given a formula $\phi$ Is $\phi \models FALSE$ equivalent to $\phi$ not SAT? Or does $\phi \models FALSE$ means that $\phi$ is never $TRUE$ and $\phi$ not SAT means, that there existst at least one ...
0
votes
1answer
198 views

Proving that a grammar generates a language

Since every context free grammar is equivalent to a Push down automaton, to show that a grammar $G$ generates a language $L$, is it sufficient to draw a PDA equivalent to $G$ and then show the PDA ...